fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 2e5 + 5;
  5.  
  6. long long n, W;
  7. long long w[MaxN], v[MaxN];
  8. long long dp[MaxN];
  9.  
  10. long long cnt = 0;
  11.  
  12. void knapsack()
  13. {
  14.     for(long long i = 1; i <= cnt; i++)
  15.     {
  16.         for(long long j = W; j >= w[i]; j--)
  17.         {
  18.             dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  19.         }
  20.     }
  21. }
  22.  
  23. int main()
  24. {
  25.     ios_base::sync_with_stdio(0);
  26.     cin.tie(0);
  27.  
  28.     cin >> n >> W;
  29.  
  30.     for(long long i = 1; i <= n; i++)
  31.     {
  32.         long long x, y, c;
  33.         cin >> x >> y >> c;
  34.  
  35.         long long k = 1;
  36.  
  37.         while(k <= c)
  38.         {
  39.             cnt++;
  40.             w[cnt] = x * k;
  41.             v[cnt] = y * k;
  42.  
  43.             c -= k;
  44.             k <<= 1;
  45.         }
  46.  
  47.         if(c)
  48.         {
  49.             cnt++;
  50.             w[cnt] = x * c;
  51.             v[cnt] = y * c;
  52.         }
  53.     }
  54.  
  55.     knapsack();
  56.  
  57.     cout << dp[W];
  58. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/95xsyB
language:
C++14 (gcc 8.3)
created:
6 hours 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!