fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[105][105];
  5. int c, n;
  6. int p[105];
  7.  
  8. int knapsack(int i, int w){
  9. if(i<0) return 0;
  10. if(w<=0) return 0;
  11. if(dp[i][w]!=-1) return dp[i][w];
  12. return dp[i][w] = max(knapsack(i-1, w), p[i] + knapsack(i-1, w-1));
  13. }
  14.  
  15. int main(){
  16. cin>>n>>c;
  17. for(int i=0; i<n; i++){
  18. int x,y;
  19. cin>>x>>y;
  20. p[i] = x*y;
  21. }
  22. for(int i=0; i<105; i++)
  23. for(int j=0; j<105; j++)
  24. dp[i][j] = -1;
  25.  
  26. cout<<knapsack(n-1,c);
  27. }
  28. /*
  29. 4 2
  30. 2 2
  31. 2 5
  32. 1 2
  33. 3 7
  34. */
  35.  
Success #stdin #stdout 0.01s 5492KB
stdin
4 2
2 2
2 5
1 2
3 7
stdout
31