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