fork download 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int oxygen[1010],nitrogen[1010],weight[1010],n;
  5. int dp[200][200];
  6. // oxy is the amnt of oxygen needed , nitro is the amnt of nitrogen needed , pos     denotes element picked up till now
  7. int calculate (int oxy , int nitro ,int pos){
  8.  
  9. long long int min = 10000000;
  10. if(oxy <=0 && nitro <=0)
  11.     return 0;
  12. if(dp[oxy+79][nitro+21]!=-1)    
  13.     return dp[oxy+79][nitro+21];
  14. else{
  15.     for(int i=pos+1;i<n;i++){
  16.  
  17.             int val = calculate (oxy - oxygen[i] ,nitro - nitrogen[i] , i)+ weight[i];
  18.  
  19.             if(val<min){
  20.                 min = val;
  21.             }
  22.         }
  23.     }
  24.     dp[oxy+79][nitro+21]=min;
  25.     return min;
  26.  
  27. }   
  28.  
  29. int main(){
  30. int test;
  31. int i,oxy,nitro;
  32. cin>>test;
  33. while(test--){
  34.     cin>>oxy>>nitro;
  35.     cin>>n;
  36.     for( i=0;i<n;i++){
  37.         cin>>oxygen[i]>>nitrogen[i]>>weight[i];
  38.     }
  39.     for(i=0;i<110;i++){
  40.         for(int j=0;j<110;j++){
  41.             dp[i][j]=-1;
  42.         }
  43.     }   
  44.  
  45.     long long int min =1000000; 
  46.     for(i=0;i<n;i++){
  47.         int val = calculate(oxy-oxygen[i],nitro-nitrogen[i], i)+weight[i];
  48.         if(val<min)
  49.             min = val;
  50.     }
  51.  
  52.     cout<<min<<endl;
  53. }
  54. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
1
22 175
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
stdout 
119
https://ideone.com/AFrw4d
1
23 176
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
language:
C++ (gcc 8.3)
created:
12 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!