fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define          fi  first
  6. #define          se  second
  7. #define  superspeed  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define  file(name)  freopen(name".inp", "r", stdin);\
  9.                      freopen(name".out", "w", stdout);
  10.  
  11. typedef                   long long  ll;
  12. typedef pair <long long, long long>  pll;
  13. typedef          vector <long long>  vll;
  14.  
  15. const ll Mod = 1e9 + 7;
  16.  
  17. ll N, M, F[100005];
  18. vll W, V;
  19.  
  20. int main() {
  21.     superspeed;
  22. #ifndef ONLINE_JUDGE
  23. 	file("dttui2");
  24. #endif
  25.     cin >> N >> M;
  26.     W.push_back(0);
  27.     V.push_back(0);
  28.     while (N--) {
  29.         ll w, v, a;
  30.         cin >> a >> w >> v;
  31.         ll pow2 = 1;
  32.         while (a >= pow2) {
  33.             a -= pow2;
  34.             W.push_back(w * pow2);
  35.             V.push_back(v * pow2);
  36.             pow2 *= 2;
  37.         }
  38.         if (a > 0) {
  39.             W.push_back(w * a);
  40.             V.push_back(v * a);
  41.         }
  42.     }
  43.     N = W.size() - 1;
  44.     for (ll i = 1; i <= N; ++i)
  45.         for (ll w = M; w >= 0; --w)
  46.             if (w >= W[i]) F[w] = max(F[w], V[i] + F[w - W[i]]);
  47.     cout << F[M];
  48.     return 0;
  49. }
  50.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
3 10
2 3 5
3 2 3
1 5 10
stdout
copy 
18
https://ideone.com/7gVTlh
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!