fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define endl '\n'
  4. #define se second
  5. #define int long long
  6. #define getName(x) #x
  7. #define vi std::vector<int>
  8. #define isz(v) (int) v.size()
  9. #define pii std::pair<int, int>
  10. #define all(v) v.begin(), v.end()
  11. #define loop cerr << "here" << endl;
  12. #define breakLoop if(TIME > 1) break;
  13. #define TIME 1.0 * clock() / CLOCKS_PER_SEC
  14. using namespace std;
  15. typedef long long ll;
  16.  
  17.  
  18. template <typename T> void maximize(T &a, T b){if(a < b) a = b;}
  19. template <typename T> void minimize(T &a, T b){if(a > b) a = b;}
  20.  
  21. int f1[20007][502], f2[20007][502];
  22. int n, t, maxw, ans[200007], cnt;
  23. pii a[20007];
  24. struct info{
  25.     int L, R, maxw, idx;
  26. };vector<info> q[200005];
  27. bool check[20005];
  28.  
  29. void dnc(int L, int R){
  30.     int mid = L + R >> 1;
  31.     if(check[mid]) return;
  32.     for(int i = L - 1; i <= R + 1; i++)
  33.         for(int j = 0; j <= maxw; j++) f1[i][j] = f2[i][j] = 0;
  34.     check[mid] = 1;
  35.  
  36.     for(int i = mid + 1; i <= R; i++){
  37.         for(int j = 1; j <= maxw; j++){
  38.             f2[i][j] = f2[i - 1][j];
  39.             if(j >= a[i].fi){
  40.                 maximize(f2[i][j], f2[i - 1][j - a[i].fi] + a[i].se);
  41.             }
  42.         }
  43.     }
  44.     for(int i = mid; i >= L; i--){
  45.         for(int j = 1; j <= maxw; j++){
  46.             f1[i][j] = f1[i + 1][j];
  47.             if(j >= a[i].fi){
  48.                 maximize(f1[i][j], (f1[i + 1][j - a[i].fi] + a[i].se) );
  49.             }
  50.         }
  51.     }
  52.     vector<info> left, right;
  53.  
  54.     for(auto i : q[mid]){
  55.         if(i.L < L or i.R > R) continue;
  56.         if(i.R < mid) left.push_back(i);
  57.         if(i.L > mid) right.push_back(i);
  58.         if(i.L < L or i.R > R or i.R < mid or i.L > mid) continue;
  59.         cnt++;
  60.         for(int w = 0; w <= i.maxw; w++)
  61.             maximize(ans[i.idx], (f2[i.R][w] + f1[i.L][i.maxw - w]));
  62.     }
  63.     if(L == R or cnt == t) return;
  64.     dnc(L, mid);
  65.     dnc(mid + 1, R);
  66.  
  67. }
  68.  
  69. signed main(){
  70.     ios::sync_with_stdio(false);
  71.     cin.tie(nullptr);
  72.     #define task "t"
  73.     if (fopen(task".inp", "r")){
  74.         freopen(task".inp", "r", stdin);
  75.         freopen(task".out", "w", stdout);
  76.     }
  77.  
  78.     cin >> n;
  79.     for(int i = 1; i <= n; i++){
  80.         cin >> a[i].fi >> a[i].se;
  81.     }
  82.     cin >> t;
  83.     for(int i = 1; i <= t; i++){
  84.         int L, R, limW;
  85.         cin >> L >> R >> limW; maximize(maxw, limW);
  86.         int lo = 1, hi = n, pos;
  87.         while(lo <= hi){
  88.             int mid = lo + hi >> 1;
  89.             if(mid > R) hi = mid;
  90.             else if(mid < L) lo = mid + 1;
  91.             else{
  92.                 pos = mid;
  93.                 break;
  94.             }
  95.         }
  96.         q[pos].push_back({L, R, limW, i});
  97.     }
  98.     //for(int i = 0; i <= n + 1; i++) f1[i].assign(maxw + 2, 0), f2[i].assign(maxw + 2, 0);
  99.  
  100.     dnc(1, n);
  101.     for(int i = 1; i <= t; i++) cout << ans[i] << endl;
  102.  
  103. }
  104.  
Success #stdin #stdout 0.01s 11660KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YHEcWN
language:
C++14 (gcc 8.3)
created:
2 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!