fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. #define pb push_back
  6. #define MAX 3005
  7.  
  8. int n,t,s;
  9. pair<int,int> a[MAX];
  10. #define fi first
  11. #define se second
  12.  
  13. void nhap()
  14. {
  15.     cin >> n >> t >> s;
  16. }
  17.  
  18. void sub1()
  19. {
  20.     for(int i = 0; i<n; i++) cin >> a[i].fi >> a[i].se;
  21.     ll ans = 0;
  22.     for(int mask = 0; mask < (1<<n); mask++){
  23.         int check = 0;
  24.         ll sum = 0;
  25.         for(int tmp = mask; tmp >0; tmp &= (tmp-1)){
  26.             int i = __builtin_ctz(tmp);
  27.             if(check < s && s < check + a[i].se) check = s;
  28.             check += a[i].se;
  29.             sum += a[i].fi;
  30.         }
  31.         if(check <= t) ans = max(ans, sum);
  32.     }
  33.     cout << ans;
  34. }
  35.  
  36. void sub2()
  37. {
  38.     for(int i = 1; i<=n; i++) cin >> a[i].fi >> a[i].se;
  39.     vector<vector<ll> > dp(n+1,vector<ll>(t+1,0));
  40.     for(int i = 1; i<=n; i++){
  41.         for(int j = 0; j<=t; j++){
  42.             dp[i][j] = max(dp[i][j], dp[i-1][j]);
  43.             if(j >= a[i].se){
  44.                 dp[i][j] = max(dp[i][j], dp[i-1][j - a[i].se] + a[i].fi);
  45.             }
  46.         }
  47.     }
  48.     ll ans = 0;
  49.     for(int i = 0; i<=t; i++) ans = max(ans, dp[n][i]);
  50.     cout << ans;
  51. }
  52.  
  53. void sub3()
  54. {
  55.     for(int i = 1; i<=n; i++) cin >> a[i].fi >> a[i].se;
  56.     vector<vector<ll> > dp(n+1, vector<ll>(t+1,0));
  57.     for(int i = 1; i<=n; i++){
  58.         for(int j = 0; j<=t; j++){
  59.             dp[i][j] = max(dp[i][j], dp[i-1][j]);
  60.             if(j >= a[i].se){
  61.                 ll prev = j - a[i].se;
  62.                 if(prev < s && s < j) continue;
  63.                 dp[i][j] = max(dp[i][j], dp[i-1][j-a[i].se] + a[i].fi);
  64.             }
  65.         }
  66.     }
  67.     ll ans = 0;
  68.     for(int i = 0; i<=t; i++) ans = max(ans, dp[n][i]);
  69.     cout << ans;
  70. }
  71.  
  72. int main()
  73. {
  74.     ios_base::sync_with_stdio(0); cin.tie(0);
  75.     freopen("SPACE.INP","r",stdin);
  76.     freopen("SPACE.OUT","w",stdout);
  77.     nhap();
  78.     if(n <= 20){
  79.         sub1();
  80.         return 0;
  81.     }
  82.     if(s == 0){
  83.         sub2();
  84.         return 0;
  85.     }
  86.     sub3();
  87.     return 0;
  88. }
  89.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HUTYTY
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!