fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3. typedef long long int ll;
  4. #define mod 1000000007
  5. ll gcd (ll a, ll b) {return ( a ? gcd(b%a, a) : b );}
  6. ll modPow(ll x,ll n,ll MOD){ll res=1;while(n>0){if(n%2 == 1){res=(res*x)%MOD;}n/=2;x=(x*x)%MOD;}return res;}
  7. ll modInverse(ll a,ll p){return modPow(a,p-2,p);}
  8.  
  9. void solve(ll wt[],ll val[],ll n,ll W)
  10. {
  11.     int i, j;
  12.    ll K[n+1][W+1];
  13.  
  14.    for (i = 0; i <= n; i++)
  15.    {
  16.        for (j = 0; j <= W; j++)
  17.        {
  18.            if (i==0 || j==0)
  19.                K[i][j] = 0;
  20.            else if (j-wt[i-1]>=0)
  21.                  K[ i ][ j ] = max(val[i-1] + K[i-1][j-wt[i-1]],  K[i-1][j]);
  22.            else
  23.                  K[ i ][ j ] = K[i-1][ j ];
  24.        }
  25.    }
  26.  cout<< K[n][W];
  27.  
  28. }
  29.  
  30.  
  31. int main()
  32. {
  33.  
  34.    ios_base::sync_with_stdio (false);
  35.    ll n,m,i,j,k;
  36.    cin>>n>>m;
  37.    ll wt[n],cost[n];
  38.  
  39.    for(i=0;i<n;i++)
  40.    cin>>wt[i]>>cost[i];
  41.  
  42.    solve(wt,cost,n,m);
  43.  
  44. }
Success #stdin #stdout 0s 16064KB
comments (?)
stdin 
4 3
3 10
2 7
2 8
1 1
stdout 
10
https://ideone.com/EiWMGd
language:
C++14 (gcc 8.3)
created:
7 years 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!