fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<fstream>
  3. #define fi(i,a,b) for(int i=(a);i<(b);i++)
  4. #define fd(i,a,b) for(int i=(a);i>(b);--i)
  5. #define infy 1e8
  6. #define llu  long long
  7.  
  8. using namespace::std;
  9.  
  10. typedef vector <int> vi;	//The following operations are defined for iterators: get value of an iterator, int x = *it; , increment and decrement iterators it1++, it2--; , compare iterators by '!=' and by '<' , add an immediate to iterator it += 20; <=> shift 20 elements forward , get the distance between iterators, int n = it2-it1; ,  Not only can they operate on any container, they may also perform, for example, range checking and profiling of container usage.
  11. 				//The type of iterator can be constructed by a type of container by appending “::iterator”, “::const_iterator”, “::reverse_iterator” or “::const_reverse_iterator” to it. use '!=' instead of '<', and 'empty()' instead of 'size() != 0' -- for some container types, it’s just very inefficient to determine which of the iterators precedes another.
  12. typedef vector<vi> vvi;		//vector< vector<int> > Matrix(N, vector<int>(M, -1));
  13. typedef pair < int, int > ii;	//Pairs are compared first-to-second element. If the first elements are not equal, the result will be based on the comparison of the first elements only; the second elements will be compared only if the first ones are equal. The array (or vector) of pairs can easily be sorted by STL internal functions.(convex hull - For example, if you want to sort the array of integer points so that they form a polygon, it’s a good idea to put them to the vector< pair<double, pair<int,int> >, where each element of vector is { polar angle, { x, y } }. One call to the STL sorting function will give you the desired order of points. )
  14. typedef vector < ii > vii;
  15. typedef vector <vii> vvii;
  16.  
  17. vector<int> o(22, infy - 1);
  18. vector < vector <int> >ausi(81, o);
  19. vector<vector < vector<int> > > dp(2, ausi);
  20. vector<llu> oc(1000, 0), nc(1000, 0), wc(1000, 0);
  21.  
  22. llu f(int i, int j, int cyls, int n)
  23. {
  24.     if(i <= 0 && j <=0) return 0;                                                                                                                  /** no requirement of oxygen or nitrogen **/
  25.     if(i >= 0 && j >= 0 && dp[n][i][j] != infy -1) return dp[n][i][j];                                                         /** result already calculated**/
  26.     else if(( (i > 0 && j <= 0)||(i <= 0 && j > 0) ) && cyls == 0 ) return infy;                                           /**if either some oxygen is req or some nitrogen but no of cylinders left is zero, cost is infy**/
  27.     else
  28.     {
  29.         if( (i <= 0 || j <= 0 ) && cyls >0) return (min(wc[cyls-1] + f(i - oc[cyls-1], j - nc[cyls-1], cyls - 1, !n), f(i, j, cyls-1, !n)) );/**if any of i, j, n is -ve, simply calcluate f() for this case, as we cant access dp[][][] for it**/
  30.         if((i > 0 && j > 0) && cyls == 0) dp[n][i][j] = infy;                                                                         /** if dp[n][i][j] hasnt been calculated yet, ...., fisrt three conditions check that we dont access any negative indices**/
  31.         else                                                                                                                                                    /**includes the case when one gas requirement is +ve, while odr is -ve **/
  32.         {
  33.  
  34.             int temp  = min(wc[cyls-1] + f(i - oc[cyls-1], j - nc[cyls-1], cyls - 1, !n), f(i, j, cyls-1, !n));
  35.             if(i >= 0 && j >= 0 && n >= 0) { dp[n][i][j] = temp; /*cout<<cyls<<' '<<n<<' '<<i<<' '<<j<<' '<<dp[n][i][j]<<endl; */return temp; }
  36.             else { /*cout<<cyls<<' '<<n<<' '<<i<<' '<<j<<' '<<temp<<endl; */return temp; }
  37.         }
  38.     }
  39. //    cout<<cyls<<' '<<n<<' '<<i<<' '<<j<<' '<<dp[n][i][j]<<endl;
  40.     return dp[n][i][j];
  41.  
  42. }
  43. void set_dp(int n)
  44. {
  45.     dp[n] = ausi;
  46.     dp[0][0][0] = 0;
  47. }
  48. int main()
  49. {
  50. //   freopen("in.txt", "r", stdin);
  51.   int t, O, N, cylinders, n = 1;
  52.   cin>>t;
  53.  
  54.   while(t--)
  55.   {
  56.       dp = vector<vector < vector<int> > > (2, ausi);
  57.       dp[0][0][0] = 0;
  58.       n  = 1;
  59.  
  60.       cin>>O>>N;
  61.       cin>>cylinders;
  62.       fi(i, 0, cylinders)
  63.       cin>>oc[i]>>nc[i]>>wc[i];
  64.  
  65. //        cout<<"cs  n  i  j  dp"<<endl;
  66.       fi(cyls, 1, cylinders+1)
  67.       {
  68.             fi(i, 0, O+1)
  69.             fi(j, 0, N+1)
  70.             f(i, j, cyls, n);
  71.             n = !n;
  72.             set_dp(n);
  73.       }
  74. n = !n;
  75. cout<<dp[n][O][N]<<endl;
  76. //n = !n;
  77. //cout<<dp[n][O][N]<<endl<<n;
  78.   }
  79.  
  80. return 0;
  81. }
  82.  
Success #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
6
5 60
5
1 2 3
6 5 7
4 8 9
21 45 56
84 44 60
7 50
6
51 14 19
51 61 29
15 84 56
18 49 33
48 59 56
32 15 84
6 40
4
23 56 25
23 65 29
98 65 87
62 94 89
20 79
8
21 45 56
14 44 60
19 14 19
15 61 49
19 64 56
18 49 43
48 59 66
32 15 24
15 78
6
13 56 55
23 65 69
18 65 73
15 69 89
15 48 53
32 65 62
19 75
6
16 65 52
21 15 21
12 8 0
12 48 1
42 19 50
70 99 79
stdout
copy 
75
29
25
80
108
51
https://ideone.com/jjFJ2p
language:
C++14 (gcc 8.3)
created:
9 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!