Submission #1870721

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <stack>
#include <queue>
using namespace std;

long long n,W,v[101],w[101],dp[101][1000001];

long long solve(long long i,long long sum){
    if(sum<0)return 0;
    if(i==n)return 0;
    if(W-sum>1000001)return max(solve(i+1,sum),solve(i+1,sum-w[i])+v[i]);
    if(dp[i][W-sum]!=0)return dp[i][W-sum];
    else{
        dp[i][W-sum]=solve(i+1,sum);
        if(sum-w[i]>=0){
            dp[i][W-sum]=max(solve(i+1,sum),solve(i+1,sum-w[i])+v[i]);
        }
        return dp[i][W-sum];
    }
}

int main(void){
    cin>>n>>W;
    for(int i=0;i<n;i++){
        cin>>w[i]>>v[i];
    }
    cout<<solve(0,W)<<endl;
    return 0;
}

Submission Info

Judge Result