Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector <int> w,v;
- int dp[2100][2100];
- int n,t,a,b,mx=0;
- int main()
- {
- scanf("%d %d",&t,&n);
- for (int i=0;i<n;i++)
- {
- scanf("%d %d",&a,&b);
- w.push_back(a);
- v.push_back(b);
- }
- for (int i=0;i<n;i++)
- {
- for (int j=0;j<=t;j++)
- {
- if (!i)
- dp[i][j]= (w[i]<=j ? v[i] : 0);
- else
- {
- dp[i][t]=dp[i-1][t];
- if (w[i]<=t)
- {
- dp[i][j]= max (dp[i][j], dp[i-1][j-w[i]]+v[i]);
- }
- }
- }
- }
- for (int i=0;i<n;i++)
- mx=max(mx,dp[i][n-1]);
- printf("%d\n",mx);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement