fork(1) download
  1. #include<stdio.h>
  2. int b1,b,n,d,a,x,y,sack[30010][60],cards[30010][2];
  3. int main()
  4. {
  5. scanf("%d%d%d",&b1,&n,&d);
  6.  
  7. for(int i=1;i<=n;i++)
  8. {
  9. scanf("%d%d",&cards[i][1],&cards[i][0]);//cards[i][0] is profit and cards[i][1] is price
  10. }
  11.  
  12. for(;d--;printf("%d\n",sack[y][b1]))
  13. {
  14.  
  15. scanf("%d%d%d%d",&a,&b,&x,&y);
  16.  
  17. for(int i=0;i<=y;i++)
  18. {
  19. for(int j=0;j<=b1;j++)
  20. {
  21. sack[i][j]=0;
  22. }
  23. }
  24.  
  25.  
  26. cards[a][1]=b;
  27.  
  28. //dp knapsack
  29.  
  30. for(int i=x;i<=y;i++)
  31. {
  32. for(int j=1;j<=b1;j++)
  33. {
  34. if(cards[i][1]<=j&&sack[i-1][j]<cards[i][0]+sack[i-1][j-cards[i][1]])
  35. {
  36. sack[i][j]=cards[i][0]+sack[i-1][j-cards[i][1]];
  37. }
  38. else
  39. {
  40. sack[i][j]=sack[i-1][j];
  41. }
  42. }
  43. }
  44. }
  45. return 0;
  46. }
Success #stdin #stdout 0s 9960KB
stdin
5 5 3
9 6
1 5
2 3
3 11
2 7
1 1 1 4
4 6 3 5
4 1 1 4
stdout
22
10
25