fork download
copy 
  1. #include<bits/stdc++.h>
  2. #include<fstream>
  3. //#include <chrono>
  4. #define fi(i,a,b) for(int i=(a);i<(b);i++)
  5. #define fd(i,a,b) for(int i=(a);i>(b);--i)
  6. #define infy 1e8
  7. #define llu  long long
  8.  
  9. using namespace::std;
  10.  
  11. 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.
  12. 				//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.
  13. typedef vector<vi> vvi;		//vector< vector<int> > Matrix(N, vector<int>(M, -1));
  14. 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. )
  15. typedef vector < ii > vii;
  16. typedef vector <vii> vvii;
  17.  
  18. vector<int> n(81, infy - 1);
  19. vector < vector <int> >ausi(22, n);
  20. vector<vector < vector<int> > > dp(2
  21.                                    , ausi);
  22. vector<llu> oc(1000, 0), nc(1000, 0), wc(1000, 0); /** oxygen, nitrogen, wieght of input cylinders**/
  23.  
  24. llu f(int i, int j, int cyls, int n)        /**oxygen required : i, nitrogen req : j, no of cylinders available : cyls, n : a variable used to alternate between 2 states (0 and 1)**/
  25. {
  26.     if(dp[n][i][j] != infy -1) return dp[n][i][j];                                                         /** result already calculated**/
  27.     dp[n][i][j]  = min((llu)wc[cyls-1] + dp[n^1][max((llu)0, i - oc[cyls-1])][max((llu)0, j - nc[cyls-1])], (llu)dp[n^1][i][j]); /**note how cleverly we pass only positive i, j this saves alot of checks which might be needed if i or j are -ve, as we need to access dp[n][i][j] **/
  28.     return dp[n][i][j];
  29. }
  30. void set_dp(int n)
  31. {
  32.     dp[n] = ausi;
  33.     dp[0][0][0] = 0;
  34. }
  35. int main()
  36. {
  37.     auto Start = chrono::steady_clock::now();
  38. //   freopen("in.txt", "r", stdin);
  39.   int t, O, N, cylinders, n = 1;
  40.   cin>>t;
  41.  
  42.   while(t--)
  43.   {
  44.       dp = vector<vector < vector<int> > > (2, ausi);
  45.       dp[0][0][0] = 0;
  46.       n  = 1;
  47.  
  48.       cin>>O>>N;                /**the amount of O and N desired **/
  49.       cin>>cylinders;           /**the no of available cylinders**/
  50.       fi(i, 0, cylinders)
  51.       cin>>oc[i]>>nc[i]>>wc[i];         /**specifications of available cylinders**/
  52.  
  53.       fi(cyls, 1, cylinders+1)          /**starting from cylinder 1 to last**/
  54.       {
  55.             fi(i, 0, O+1)
  56.             fi(j, 0, N+1)
  57.             dp[n][i][j]  = min((llu)wc[cyls-1] + dp[n^1][max((llu)0, i - oc[cyls-1])][max((llu)0, j - nc[cyls-1])], (llu)dp[n^1][i][j]);
  58.             n ^= 1;
  59.             /**f(i, j, cyls, n);                 recursi11`1`on variant, slower than first method as it costs various redundant calls (dp can be used to get immediate result while f() needs to be called with parameters as indices of dp[][][]
  60.             set_dp(n);**/
  61.       }
  62. n = !n;  /**this adjustment gives us the right dp array, as n is toggled various times to alternate bw two states**/
  63. cout<<dp[n][O][N]<<endl;
  64.   }
  65. auto End = chrono::steady_clock::now();
  66. cout<<chrono::duration < double, nano> (End - Start).count()<<" ns"<<endl;
  67. return 0;
  68. }
  69.  
  70.  
  71.  
Success #stdin #stdout 0s 3468KB
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
616218 ns
https://ideone.com/uqtYAR
language:
C++14 (gcc 8.3)
created:
8 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!