fork download
copy 
  1. /*
  2.     Author: Nguyen Nhut Truong
  3.     From Chuyen Tien Giang High School For The Gifed
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. //#define int long long
  9. #define start signed main
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define eb emplace_back
  14. #define il pair<int,ll>
  15. #define ii pair<int,int>
  16. #define len(s) (int)s.size()
  17. #define all(s) (s).begin(),(s).end()
  18. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  19.  
  20. #define MASK(x) ((1LL)<<(x))
  21. #define Bit(x,i) (((x)>>(i))&1)
  22. #define Countbit(x) __builtin_popcountll(x)
  23.  
  24. typedef long long ll;
  25. typedef long double ld;
  26.  
  27. int dx[]={1,-1,0,0,-1,1,1,-1};
  28. int dy[]={0,0,1,-1,-1,-1,1,1};
  29.  
  30. template <class C> bool Minimize(C &a, C b) { if (a>b) { a=b; return true; } return false;}
  31. template <class C> bool Maximize(C &a, C b) { if (a<b) { a=b; return true; } return false;}
  32.  
  33. inline ll add(ll a,ll b,ll c) { return (a+b)%c; };
  34. inline ll sub(ll a,ll b,ll c) { return (a-b+c)%c; };
  35. inline ll mul(ll a,ll b,ll c) { return ((a%c)*(b%c))%c; };
  36.  
  37. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  38.  
  39. ll rand(ll l,ll r){
  40.     assert(l<=r);
  41.     return l+rd()%(r-l+1);
  42. }
  43.  
  44. void MakeInp() {
  45.     ofstream cout("Task.inp");
  46.  
  47.     cout.close();
  48. }
  49.  
  50. /// Constant Limit
  51.  
  52. const int N=1e4+5,M=1e3+5,INF=1e9,lim=1e6;
  53. const int block=448,base=31;
  54.  
  55. ll Mod=1e9+7,Mod_base=1777777777,LNF=1e18;
  56.  
  57. ///____________________________________________________________________________________________________________________________
  58.  
  59. int n,q,w[N],c[N];
  60. int dp[N][105];
  61.  
  62. int mask[N];
  63. int ans[10*N];
  64.  
  65. vector<int> p[20];
  66.  
  67. struct cd{
  68.     int l,r,w,id;
  69. };
  70. vector <cd> query[N];
  71.  
  72. void get(int l,int r,int lv)
  73. {
  74.     if(l>r || l==r) return ;
  75.  
  76.     int mid=(r+l)>>1;
  77.  
  78.     for(int i=mid+1;i<=r;i++) mask[i]|=(1<<lv);
  79.  
  80.     p[lv].push_back(mid);
  81.     get(l,mid,lv+1);
  82.     get(mid+1,r,lv+1);
  83. }
  84.  
  85. void DnC(int l,int r) {
  86.     if(l>r || l==r) return;
  87.  
  88.     for (int i=l;i<=r;i++) memset(dp[i],0,sizeof dp[i]);
  89.  
  90.     int mid=(r+l)>>1;
  91.     for(int j=w[mid];j<=100;j++) dp[mid][j]=c[mid];
  92.  
  93.     for (int i=mid-1;i>=l;i--)
  94.     for (int j=1;j<=100;j++) {
  95.         if(j>=w[i]) Maximize(dp[i][j],dp[i+1][j-w[i]]+c[i]);
  96.         Maximize(dp[i][j],dp[i][j-1]);
  97.         Maximize(dp[i][j],dp[i+1][j]);
  98.     }
  99.  
  100.     for(int j=w[mid+1];j<=100;j++) dp[mid+1][j]=c[mid+1];
  101.  
  102.     for (int i=mid+2;i<=r;i++)
  103.     for (int j=1;j<=100;j++) {
  104.         if(j >= w[i]) Maximize(dp[i][j],dp[i-1][j-w[i]]+c[i]);
  105.         Maximize(dp[i][j],dp[i][j-1]);
  106.         Maximize(dp[i][j],dp[i-1][j]);
  107.     }
  108.  
  109.     for(cd i:query[mid]) {
  110.         for (int j=0;j<=i.w;j++)
  111.         ans[i.id]=max(ans[i.id] ,dp[i.r][i.w-j]+dp[i.l][j]);
  112.     }
  113.  
  114.     DnC(l,mid);
  115.     DnC(mid+1,r);
  116. }
  117.  
  118.  
  119. start() {
  120.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  121.     OpenFile("TASK");
  122.  
  123.     cin>>n;
  124.  
  125.     for (int i=1;i<=n;i++) cin>>w[i]>>c[i];
  126.     get(1,n,0);
  127.  
  128.     cin>>q;
  129.     for(int i=1;i<=q;i++) {
  130.         cd t;
  131.         cin>>t.l>>t.r>>t.w;
  132.  
  133.         t.id=i;
  134.         if(t.l==t.r) {
  135.             if(w[t.l]<=t.w) ans[i]=c[t.l];
  136.         } else {
  137.             int id=__builtin_ctz(mask[t.l]^mask[t.r]);
  138.             int mid=*lower_bound(all(p[id]),t.l);
  139.             query[mid].push_back(t);
  140.         }
  141.     }
  142.  
  143.     DnC(1,n);
  144.  
  145.     for (int i=1;i<=q;i++) cout << ans[i] << '\n';
  146.  
  147.  
  148.  
  149.  
  150.     //cerr<<"\nBien dich thanh cong\nTime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  151.     return 0;
  152. }
  153.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R2EK5b
language:
C++14 (clang 8.0)
created:
14 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!