Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1145141919810364364
#define REP(i,n) for (int i=0;i<(n);i++)
typedef pair<int,int> P;
int dp[10001][51]={};
signed main() {
int W,N,K,ans=0;
cin>>W>>N>>K;
for(int i=0;i<N;i++){
int a,b; cin>>a>>b;
for(int j=W;j>=1;j--){
for(int k=K-1;k>=1;k--){
if(dp[j][k]!=0&&(j+a)<=W){
dp[j+a][k+1]=max(dp[j][k]+b,dp[j+a][k+1]);
ans=max(ans,dp[j+a][k+1]);
}
}
}
dp[a][1]=max(b,dp[a][1]);
ans=max(ans,dp[a][1]);
}
cout<<ans<<endl;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment