fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N=1e5+5;
  5. const int inf=1e18;
  6. int n,q;
  7. int m[N],g[N],d[N],f[N],s[N];
  8. int st[N*4];
  9. void update(int id,int l,int r,int u,int val){
  10.     if(l>u||r<u)return ;
  11.     if(l==r){st[id]=val;return;}
  12.     int mid=(l+r)>>1;
  13.     //cout<<l<<' '<<mid<<' '<<r<<'\n';
  14.     update(id<<1,l,mid,u,val);
  15.     update(id<<1|1,mid+1,r,u,val);
  16.     st[id]=min(st[id<<1],st[id<<1|1]);
  17. }
  18. int get(int id,int l,int r,int u,int v){
  19.     if(l>v||u>r)return inf;
  20.     if(u<=l&&r<=v)return st[id];
  21.     int mid=(l+r)>>1;
  22.     return min(get(id<<1,l,mid,u,v),
  23.                get(id<<1|1,mid+1,r,u,v));
  24. }
  25. main()
  26. {
  27.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  28.     freopen("collect.inp","r",stdin);
  29.     freopen("collect.out","w",stdout);
  30.     cin>>n;
  31.     for(int i=1;i<=n;i++)cin>>m[i];
  32.     for(int i=1;i<n;i++)cin>>d[i];
  33.     for(int i=1;i<=n;i++)cin>>g[i];
  34.     cin>>q;
  35.     if(n<=1000){
  36.         while(q--){
  37.             int W;cin>>W;
  38.             vector<int>dp(n+2,inf);
  39.             dp[0]=0;
  40.             for(int i=1;i<=n;i++){
  41.                 dp[i]=min(dp[i],dp[i-1]+g[i]*2);
  42.                 int cost=g[i],c=W-m[i];
  43.                 for(int j=i+1;j<=n;j++){
  44.                     if(c-m[j]<0)continue;
  45.                     cost+=d[j-1];
  46.                     c-=m[j];
  47.                     dp[j]=min(dp[j],dp[i-1]+cost+g[j]);
  48.                     //if(j==3)cout<<i<<' '<<dp[i]<<' '<<dp[i-1]<<' '<<cost<<' '<<g[j]<<' '<<d[i-1]<<'\n';
  49.                 }
  50.             }
  51.             //for(int i=1;i<=n;i++)cout<<dp[i]<<' ';
  52.             cout<<dp[n]<<'\n';
  53.         }
  54.         return 0;
  55.     }
  56.     for(int i=1;i<n;i++)f[i]=f[i-1]+d[i];
  57.     for(int i=1;i<=n;i++)s[i]=s[i-1]+m[i];
  58.     while(q--){
  59.         int W;cin>>W;
  60.         vector<int>dp(n+2,inf);
  61.         dp[0]=0;
  62.         dp[1]=g[1]*2;
  63.         update(1,1,n,1,dp[0]+g[1]-f[0]);
  64.         //cout<<get(1,1,n,1,1)<<' ';
  65.         for(int i=2;i<=n;i++){
  66.             //cout<<i<<':';
  67.             dp[i]=min(dp[i],dp[i-1]+g[i]*2);
  68.             //cout<<dp[i]<<' ';
  69.             int l=0,r=i-1,kq=-1;
  70.             while(l<=r){
  71.                 int mid=(l+r)>>1;
  72.                 if(s[i]-s[mid-1]<=W)kq=mid,r=mid-1;
  73.                 else l=mid+1;
  74.             }
  75.             if(kq!=-1)dp[i]=min(dp[i],get(1,1,n,kq,i-1)+g[i]+f[i-1]);
  76.             //cout<<kq<<' '<<dp[i]<<' '<<g[i]<<' '<<f[i-1]<<' ';
  77.             update(1,1,n,i,dp[i-1]+g[i]-f[i-1]);
  78.             //cout<<'\n';
  79.         }
  80.         cout<<dp[n]<<'\n';
  81.     }
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AgX2zW
language:
C++14 (gcc 8.3)
created:
5 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!