fork download
copy 
  1. #include<iostream>
  2. using namespace std;
  3. #include<math.h>
  4.  
  5. int main()
  6. {
  7. int N;
  8.     scanf("%d",&N);
  9.     while(N--)
  10.     {
  11.  
  12.     int c,n;
  13.     cin>>c>>n;
  14.              if((c==0)&&(n==0))
  15.                break;
  16.                int w[n+1],b[n+1];
  17.                for(int i=1;i<=n;i++)
  18.                cin>>w[i]>>b[i];
  19.  
  20.                int final[n+1][c+1];
  21.                int count[n+1][c+1];
  22.                for(int i=0;i<=c;i++)
  23.                final[0][i]=0;
  24.                for(int i=0;i<=n;i++)
  25.                count[0][i]=0;
  26.                for(int j=1;j<=n;j++)
  27.                {
  28.                        for(int i=0;i<=c;i++)
  29.                        {
  30.                                if(i<w[j])
  31.                                {                                         
  32.                                final[j][i]=final[j-1][i];
  33.                                count[j][i]=count[j-1][i];
  34.                                }
  35.                                else
  36.                                {       int  x=b[j]+final[j-1][i-w[j]];
  37.                                         int y=final[j-1][i];
  38.                                         if(x>y)
  39.                                         {
  40.                                             final[j][i] = x;
  41.                                             count[j][i] = w[j]+count[j-1][i-w[j]];
  42.                                         }
  43.                                          else if(x==y)
  44.                                         {
  45.                                               final[j][i] = x;
  46.                                               count[j][i] = min(count[j-1][i] , count[j-1][i-w[j]]+w[j]);
  47.                                         }
  48.                                         else
  49.                                         {
  50.                                          final[j][i]=y;
  51.                                          count[j][i]=count[j-1][i];
  52.                                         }
  53.                                }
  54.                        }
  55.                }
  56.               // cout<<count[n][c]<<" ";
  57.                cout<<"Hey stupid robber, you can get "<<final[n][c]<<"."<<endl;
  58.  
  59.     }
  60.     return 0;
  61. }
  62.  
  63.  
  64.  
  65.  
Runtime error #stdin #stdout 0.01s 2724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8CHqN
language:
C++ (gcc 8.3)
created:
14 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!