fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. #define rep(i, n) for(int i = 1; i <= n; ++i)
  8. #define forn(i, l, r) for(int i = l; i <= r; ++i)
  9. #define ford(i, r, l) for(int i = r; i >= l; --i)
  10. #define FOR(i, n) for(int i = 0; i < n; ++i)
  11. #define fi first
  12. #define se second
  13. #define pii pair<int, int>
  14. #define pll pair<ll, ll>
  15. #define pb push_back
  16. #define task "note"
  17. #define endl "\n"
  18. #define sz(a) int(a.size())
  19. #define bit(i, mask) (mask >> i & 1)
  20. #define all(a) (a).begin(), (a).end()
  21.  
  22. template<typename T> bool maximize(T &res, const T &val) { if (res <= val){ res = val; return true; }; return false; }
  23. template<typename T> bool minimize(T &res, const T &val) { if (res >= val){ res = val; return true; }; return false; }
  24. template<typename T> void printArr(T arr)
  25. {
  26.     for(auto i : arr) cout << i << " ";
  27.     cout << endl;
  28. }
  29. const int N = 5e3 + 3;
  30. const int S = 5e3 + 3;
  31. int n, max_weight;
  32. struct Knapsack
  33. {
  34.     int dp_front[N][S + 1];
  35.     int dp_back[N][S + 1];
  36.     int w[N], v[N];
  37.     int cur_front = 0, cur_back = 0;
  38.     void addFront(int weight, int value)
  39.     {
  40.         ++cur_front;
  41.         w[cur_front] = weight;
  42.         v[cur_front] = value;
  43.         // cout << "Debug: " << cur_front << endl;
  44.         // cout << weight << " " << value << endl;
  45.         assert(cur_front >= 0);
  46.         forn(j, 0, max_weight)
  47.         {
  48.             dp_front[cur_front][j] = dp_front[cur_front - 1][j];
  49.             if(j >= weight)
  50.                 maximize(dp_front[cur_front][j],
  51.                          dp_front[cur_front - 1][j - weight] + value);
  52.         }
  53.     }
  54.  
  55.     void pop_back()
  56.     {
  57.         if(cur_back == 0)
  58.         {
  59.             cur_back = 0;
  60.             ford(i, cur_front, 1)
  61.             {
  62.                 ++cur_back;
  63.                 forn(j, 0, max_weight)
  64.                 {
  65.                     dp_back[cur_back][j] = dp_back[cur_back - 1][j];
  66.                     if(j >= w[i])
  67.                         maximize(dp_back[cur_back][j],
  68.                                 dp_back[cur_back - 1][j - w[i]] + v[i]);
  69.                 }
  70.             }
  71.             cur_front = 0;
  72.         }
  73.         cur_back--;
  74.     }
  75.     int get()
  76.     {
  77.         int res = 0;
  78.         // cout << cur_front << " " << cur_back << endl;
  79.         // cout << dp_front[cur_front][2] << endl;
  80.         assert(cur_front >= 0);
  81.         assert(cur_back >= 0);
  82.         forn(j, 0, max_weight)
  83.             maximize(res, dp_front[cur_front][j] + dp_back[cur_back][max_weight - j]);
  84.         return res;
  85.     }
  86. } dq;
  87.  
  88. int w[N], v[N];
  89. int q;
  90.  
  91.  
  92.  
  93. void solve()
  94. {
  95.     cin >> n >> max_weight;
  96.     rep(i, n) cin >> w[i] >> v[i];
  97.     cin >> q;
  98.     vector<array<int, 3>> queries;
  99.     rep(i, q)
  100.     {
  101.         int l, r;
  102.         cin >> l >> r;
  103.         queries.push_back({l, r, i});
  104.     }
  105.     sort(all(queries));
  106.     vector<int> res(q + 1);
  107.     int r = 0;
  108.     int l = 1;
  109.     auto push = [&](int pos)
  110.     {
  111.         dq.addFront(w[pos], v[pos]);
  112.     };
  113.     auto pop = [&] ()
  114.     {
  115.         dq.pop_back();
  116.     };
  117.  
  118.     for(auto &[lq, rq, id] : queries)
  119.     {
  120.         while(r < rq) push(++r);
  121.         while(l < lq) l++, pop();
  122.         // cout << lq << " " << rq << " " << id << endl;
  123.         // cout << l << " " << r << endl;
  124.         res[id] = dq.get();
  125.     }
  126.     rep(i, q) cout << res[i] << endl;
  127. }
  128.  
  129. signed main()
  130. {
  131.  
  132.     ios_base::sync_with_stdio(0);
  133.     cin.tie(0); cout.tie(0);
  134. //    if(fopen(task".inp", "r"))
  135. //    {
  136. //        freopen(task".inp", "r", stdin);
  137. //        freopen(task".out", "w", stdout);
  138. //    }
  139.     int TC = 1;
  140.  
  141.     while(TC--)
  142.     {
  143.         solve();
  144.         cout << endl;
  145.     }
  146.  
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/kckPJ0
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
9 days 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!