fork download 
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<iostream>
  4.  
  5. #define INF 0x7FFFFFFF
  6.  
  7. using namespace std;
  8.  
  9. int o,n,num,ox[2000],nt[2000],wt[2000];
  10. int dp[2000][2000];
  11.  
  12. int dive(int index,int oxygen,int nitrogen,int weight) {
  13.     if(dp[oxygen][nitrogen] != -1) return dp[oxygen][nitrogen];
  14.     int &ret=dp[oxygen][nitrogen];
  15.     if(oxygen >= o && nitrogen >= n) {
  16.         ret=weight; 
  17.         return ret;
  18.     }
  19.     if(index==num) {
  20.         ret=INF;
  21.         return ret;
  22.     }
  23.     ret= min(dive(index + 1,
  24.                   oxygen + ox[index],
  25.                   nitrogen + nt[index],
  26.                   weight + wt[index]),
  27.              dive(index + 1, oxygen, nitrogen, weight));  
  28.     return ret;
  29. }
  30.  
  31. main() {
  32.     int c;
  33.     scanf("%d",&c);
  34.     while(c--) {
  35.         memset(dp,-1,sizeof(dp));
  36.         scanf("%d%d",&o,&n);
  37.         scanf("%d",&num);
  38.         for(int i=0;i<num;++i) {
  39.             scanf("%d%d%d",&ox[i],&nt[i],&wt[i]);
  40.         }
  41.         printf("%d\n",dive(0,0,0,0));
  42.     }
  43.     return 0;
  44. }
Success #stdin #stdout 0.01s 18952KB
comments (?)
stdin 
1
21 79
5
1 1 800
1 1 800
1 1 800
1 1 800
17 75 800
stdout 
2147483647
https://ideone.com/mlUYkp
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!