Submission #1870783

---

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][101][301];

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

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

Submission Info

Judge Result