fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. class kanp{
  6. public:
  7.     ll weight, profit;
  8. };
  9.  
  10. bool cmp(kanp sack1, kanp sack2)
  11. {
  12.     return sack1.profit < sack2.profit;
  13. }
  14.  
  15. ll traditional_kanp_sack(kanp sack[], ll primes[], ll N, ll W)
  16. {
  17.         //dp[N][P][W]
  18.  
  19.         ll ***dp = new ll**[2];
  20.  
  21.         for(ll i = 0; i < 2; i++)
  22.            dp[i] = new ll*[11];
  23.  
  24.         for(ll i = 0; i < 2; i++)
  25.            for(ll j = 0; j < 11; j++)
  26.               dp[i][j] = new ll[W + 1]();
  27.  
  28.         ll n, p, ans1, ans2;
  29.  
  30.         for(ll i = 1; i <= N; i++)
  31.         {
  32.            n = i & 1;
  33.  
  34.            for(ll j = 1; j < 11; j++)
  35.            {
  36.                p = j;
  37.  
  38.                for(ll w = 1; w <= W; w++)
  39.                {
  40.                    //cout << n << "  " << p << "  " << w << "\n";
  41.  
  42.                    dp[n][p][w] = dp[n ^ 1][p][w];
  43.  
  44.                    ans1 = ans2 = INT_MIN;
  45.  
  46.                    if(w >= sack[i].weight)
  47.                    {
  48.                        ans1 = dp[n ^ 1][p][w - sack[i].weight] + sack[i].profit;
  49.  
  50.                        ans2 = dp[n ^ 1][p - 1][w - sack[i].weight] + (sack[i].profit * primes[p]);
  51.                    }
  52.  
  53.                    ans1 = max(ans1, ans2);
  54.  
  55.                    dp[n][p][w] = max(dp[n][p][w], ans1);
  56.                }
  57.            }
  58.  
  59.         }
  60.  
  61.         ans1 = dp[N & 1][10][W];
  62.  
  63.         for(ll i = 0; i < 2; i++)
  64.           for(ll j = 0; j < 11; j++)
  65.             delete [] dp[i][j];
  66.  
  67.         for(ll i = 0; i < 2; i++)
  68.            delete [] dp[i];
  69.  
  70.            delete [] dp;
  71.  
  72.     return ans1;       
  73. }
  74.  
  75. int main()
  76. {
  77.    ll t;
  78.  
  79.    t = 1;
  80.  
  81.    while(t--)
  82.    {
  83.  
  84.     ll N, W;
  85.  
  86.     cin >> N >> W;
  87.  
  88.     kanp sack[N + 1];
  89.  
  90.     sack[0].weight = sack[0].profit = 0;
  91.  
  92.     for(ll i = 1; i <= N; i++)
  93.         cin >> sack[i].profit >> sack[i].weight;;
  94.  
  95.     sort(sack, sack + N, cmp);
  96.  
  97.     ll primes[11] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
  98.  
  99.     ll value = traditional_kanp_sack(sack, primes, N, W);
  100.  
  101.     cout << value << "\n";
  102.  
  103.   }
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0s 4452KB
comments (?)
stdin
copy 
3 4
1 1
2 1
3 1
stdout
copy 
152
https://ideone.com/kzotQX
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!