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
comments (?)
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
https://ideone.com/f3QHdw
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!