fork(3) download 
  1. #include <bits/stdc++.h>
  2. #define INF 400000000000
  3. #define MOD 1000000007
  4. #define MAXN 1000005
  5. #define ins insert
  6. #define pb push_back
  7. #define mp make_pair
  8. #define sz size
  9. #define rep(i, n) for(int i = 0; i < n; ++i)
  10. #define sd(n) scanf("%d",&n)
  11. #define sll(n) scanf("%I64d",&n)
  12. #define pdn(n) printf("%d\n",n)
  13. #define plln(n) printf("%I64d\n",n)
  14. #define pd(n) printf("%d ",n)
  15. #define nl() printf("\n")
  16. using namespace std;
  17.  
  18. typedef long long ll;
  19. typedef unsigned long long ull;
  20. typedef vector<ll> vi;
  21. typedef vector<vi> vii;
  22. typedef pair<ll, ll> pii;
  23.  
  24. ll n, m; vector< pair<pii, ll> > a;
  25.  
  26. ll dp[10005][701][2];
  27.  
  28. ll solve(ll idx, ll rem, ll act) {
  29.     if(idx == 0) {
  30.         if(rem-a[idx].first.second < 0) {
  31.             if(act <= 1 && (rem-a[idx].first.second+a[idx].second >= 0))
  32.                 return a[idx].first.first;
  33.             return 0;
  34.         }
  35.         return a[idx].first.first;
  36.     }
  37.     if(dp[idx][rem][act] != -1)
  38.         return dp[idx][rem][act];
  39.     ll x = a[idx].first.first+solve(idx-1, rem+a[idx].second-a[idx].first.second, act+1);
  40.     ll y = a[idx].first.first+solve(idx-1, rem-a[idx].first.second, act);
  41.     ll ans = 0;
  42.     if(rem-a[idx].first.second >= 0)
  43.         ans = max(ans, y);
  44.     if(rem+a[idx].second-a[idx].first.second >= 0 && (act <= 1))
  45.         ans = max(ans, x);
  46.  
  47.     return dp[idx][rem][act] = max(ans, solve(idx-1, rem, act));
  48. }
  49.  
  50. int main() {
  51.     ios_base::sync_with_stdio(0);
  52.     cin.tie(0);
  53.     cout.tie(0);
  54.     cin >> n >> m;
  55.     memset(dp, -1, sizeof dp);
  56.     rep(i, n) {
  57.         ll pi, wi, di;
  58.         cin >> pi >> wi >> di;
  59.         a.pb(mp(mp(pi, wi), di));
  60.     }
  61.     ll ans = solve(n-1, m, 0);
  62.     cout << ans;    
  63.     return 0;
  64. }
Runtime error #stdin #stdout 0.12s 112832KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/hPM1Ud
language:
C++14 (gcc 8.3)
created:
9 years 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!