Submission #3216449

---

Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
	
using namespace std;
const int MAX_N=100;
ll dp[MAX_N+1][MAX_N*3+1];
int N;
ll W,w[MAX_N],v[MAX_N];
int main(){
	cin>>N>>W;
	REP(i,N){
		cin>>w[i]>>v[i];
	}
	REP(i,N){
		for(int n=i+1;n>=1;n--){
			REP(j,3*N+1){
				if (j-(w[i]-w[0])>=0){
					dp[n][j]=max(dp[n][j],dp[n-1][j-(w[i]-w[0])]+v[i]);
				}
			}
		}
	}
	ll ans=0;
	REP(i,N){
		REP(j,3*N+1){
			if ((i+1)*w[0]+j<=W){
				ans=max(ans,dp[i+1][j]);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result