fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. const int N = 2e5 + 5, mod = 1e9 + 7, LG = 20;
  5. vector <vector <array <int, 3>>> dp;
  6. int n, h, d[105], s[105], id[105];
  7. vector <int> ans;
  8.  
  9. array <int, 3> solve(int idx, int time) {
  10.     if (time > h)
  11.         return {(int)-1e9, (int)1e9, (int)1e9};
  12.     if (idx == n || time >= h)
  13.         return {0, 0, 0};
  14.     auto &ret = dp[idx][time];
  15.     if (~ret[0])
  16.         return ret;
  17.     ret = solve(idx + 1, time);
  18.  
  19.     auto res = solve(idx + 1, time + d[idx]);
  20.     res[0] += s[idx];
  21.     res[1] += d[idx] + time;
  22.     res[2] = id[idx];
  23.     if (ret[0] == res[0]) {
  24.         if (ret[1] > res[1])
  25.             ret = res;
  26.         else if (ret[1] == res[1]) {
  27.             if (ret[2] > res[2])
  28.                 ret = res;
  29.         }
  30.     }
  31.     else if (res[0] > ret[0])
  32.         ret = res;
  33.     return ret;
  34.  
  35. }
  36.  
  37. void build(int idx, int time) {
  38.     if (time > h)
  39.         return;
  40.     if (idx == n || time >= h)
  41.         return;
  42.     auto &ret = dp[idx][time];
  43.  
  44.     if (ret == solve(idx + 1, time)) {
  45.         build(idx + 1, time);
  46.         return;
  47.     }
  48.     ans.push_back(id[idx]);
  49.     build(idx + 1, time + d[idx]);
  50. }
  51. void burn() {
  52.     cin >> n >> h;
  53.     h *= 60;
  54.     vector <array <int, 3>> vec(n);
  55.     for (int i = 0; i < n; i++)
  56.         cin >> d[i], d[i] *= 2, d[i] /= 100, vec[i][0] = d[i];
  57.     for (int i = 0; i < n; i++)
  58.         cin >> s[i], vec[i][2] = s[i], vec[i][1] = i+1;
  59.     sort(vec.begin(), vec.end());
  60.  
  61.     for (int i = 0; i < n; i++)
  62.         d[i] = vec[i][0], s[i] = vec[i][2], id[i] = vec[i][1];
  63.     array <int, 3> tmp = {-1, -1, -1};
  64.     dp = vector <vector <array <int, 3>>> (n, vector <array <int, 3>> (h, tmp));
  65.  
  66.     auto res = solve(0, 0);
  67.     build(0, 0);
  68.  
  69.     for (auto &a : ans)
  70.         cout << a << ' ';
  71.     cout << '\n';
  72.     ans.clear();
  73.  
  74.  
  75. }
  76.  
  77. signed main()
  78. {
  79.     ios_base::sync_with_stdio(false);
  80.     cin.tie(nullptr);
  81.     int t = 1;
  82.     cin >> t;
  83.     while(t--)
  84.         burn();
  85. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/A8ggff
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
1 hour 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!