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