fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<algorithm>
  6. #include<map>
  7. #include<vector>
  8. #define MOD 1000000007
  9. #define INF 1000000000
  10. #define gc getchar_unlocked
  11. #define ll long long
  12. #define ull unsigned long long
  13. using namespace std;
  14.  
  15. inline void scanint(int &x){
  16.   register int c = gc();
  17.   x = 0;
  18.   for(;(c<48 || c>57);c = gc());
  19.   for(;c>47 && c<58;c = gc()){
  20.     x = (x<<1) + (x<<3) + c - 48;
  21.   }
  22. }
  23.  
  24. inline void scanint(unsigned int &x){
  25.   register unsigned int c = gc();
  26.   x = 0;
  27.   for(;(c<48 || c>57);c = gc());
  28.   for(;c>47 && c<58;c = gc()){
  29.     x = (x<<1) + (x<<3) + c - 48;
  30.   }
  31. }
  32.  
  33. inline void scanint(ull &x){
  34.   register ull c = gc();
  35.   x = 0;
  36.   for(;(c<48 || c>57);c = gc());
  37.   for(;c>47 && c<58;c = gc()){
  38.     x = (x<<1) + (x<<3) + c - 48;
  39.   }
  40. }
  41.  
  42. inline void scanint(ll &x){
  43.   register ll c = gc();
  44.   x = 0;
  45.   for(;(c<48 || c>57);c = gc());
  46.   for(;c>47 && c<58;c = gc()){
  47.     x = (x<<1) + (x<<3) + c - 48;
  48.   }
  49. }
  50.  
  51. int dp[1002][23][81];
  52. int ox[1002],nt[1002],wt[1002];
  53.  
  54. void solve(int n, int oxy, int nit){
  55.   for(int i = 0; i <=n; ++i)
  56.     for(int j = 0; j <= oxy; ++j)
  57.       for(int k = 0; k <= nit; ++k){
  58. 	if(i == 0)
  59. 	  dp[i][j][k] = INF;
  60. 	else if(j == 0 && k == 0)
  61. 	  dp[i][j][k] = 0;
  62. 	else
  63. 	  dp[i][j][k] = min(dp[i-1][j][k], dp[i-1][max(j-ox[i], 0)][max(k-nt[i], 0)] + wt[i]);
  64.       }
  65.   printf("%d\n", dp[n][oxy][nit]);
  66. }
  67.  
  68. int main(){
  69.   int t,oxy,nit,n;
  70.   scanint(t);
  71.   while(t--){
  72.     scanint(oxy);
  73.     scanint(nit);
  74.     scanint(n);
  75.     for(int i = 1; i<=n; ++i){
  76.       scanint(ox[i]);
  77.       scanint(nt[i]);
  78.       scanint(wt[i]);
  79.     }
  80.     solve(n, oxy, nit);
  81.   }
  82.   return 0;
  83. }
  84.  
Success #stdin #stdout 0s 10408KB
comments (?)
stdin
copy 
1
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
stdout
copy 
249
https://ideone.com/PrCFc9
language:
C++ (gcc 8.3)
created:
10 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!