Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<vector>
- #include<algorithm>
- #include<set>
- #include<map>
- #include<queue>
- #define ls(x) (x<<1)
- #define rs(x) (x<<1|1)
- #define pb push_back
- #define MP make_pair
- using namespace std;
- typedef long long LL;
- const int maxn=3005;
- const int maxm=8205;
- const LL INF=100000000000000;
- int n;
- LL dist[maxn];
- int D[maxn],cst[maxn];
- int pt[maxn];
- LL F[maxn][maxn][2];
- struct Seg{
- LL mi[maxm];
- void pushup(int x)
- {
- mi[x]=min(mi[ls(x)],mi[rs(x)]);
- }
- void build(int x,int l,int r)
- {
- mi[x]=INF;
- if(l==r)
- return;
- int mid=(l+r)>>1;
- build(ls(x),l,mid),build(rs(x),mid+1,r);
- pushup(x);
- }
- void update(int x,int l,int r,int pos,LL k)
- {
- if(l==r){
- mi[x]=k;
- return;
- }
- int mid=(l+r)>>1;
- if(pos<=mid)
- update(ls(x),l,mid,pos,k);
- else
- update(rs(x),mid+1,r,pos,k);
- pushup(x);
- }
- LL query(int x,int l,int r,int ql,int qr)
- {
- if(r<ql||l>qr)
- return INF;
- if(l>=ql&&r<=qr)
- return mi[x];
- int mid=(l+r)>>1;
- return min(query(ls(x),l,mid,ql,qr),query(rs(x),mid+1,r,ql,qr));
- }
- }G[maxn][2],H[maxn][2];
- void readin()
- {
- scanf("%d",&n);
- for(int i=3;i<=n+1;++i)
- scanf("%lld",&dist[i]),dist[i]+=dist[i-1];
- for(int i=2;i<=n+1;++i)
- scanf("%d",&D[i]);
- for(int i=1;i<=n+1;++i)
- scanf("%d",&cst[i]);
- n+=2;
- dist[n]=dist[n-1];
- }
- void update_pt(int l,int r)
- {
- while(pt[l]<r-1){
- if(F[l][pt[l]][1]>=F[pt[l]][r][0])
- break;
- ++pt[l];
- }
- }
- inline LL max(LL x,LL y)
- {
- return x>y?x:y;
- }
- inline LL min(LL x,LL y)
- {
- return x<y?x:y;
- }
- void calc(int l,int r)
- {
- update_pt(l,r);
- int pos=pt[l];
- F[l][r][0]=F[l][r][1]=INF;
- if(F[l][pos][1]>=F[pos][r][0]){
- F[l][r][0]=min(F[l][r][0],G[l][1].query(1,1,n,pos,r-1)-dist[l]);
- F[l][r][1]=min(F[l][r][1],H[l][1].query(1,1,n,pos,r-1)+dist[r]);
- }
- if(F[l][pos][1]<F[pos][r][0])
- ++pos;
- if(pos>l+1){
- F[l][r][0]=min(F[l][r][0],G[r][0].query(1,1,n,l+1,pos-1)-dist[l]);
- F[l][r][1]=min(F[l][r][1],H[r][0].query(1,1,n,l+1,pos-1)+dist[r]);
- }
- G[l][1].update(1,1,n,r,F[l][r][1]+dist[r]+D[r]);
- G[r][0].update(1,1,n,l,F[l][r][0]+dist[l]+D[l]);
- H[l][1].update(1,1,n,r,F[l][r][1]-dist[r]+D[r]);
- H[r][0].update(1,1,n,l,F[l][r][0]-dist[l]+D[l]);
- }
- void init()
- {
- for(int i=1;i<=n;++i){
- pt[i]=i+1;
- for(int j=0;j<=1;++j)
- G[i][j].build(1,1,n),H[i][j].build(1,1,n);
- }
- }
- void work()
- {
- init();
- for(int i=2;i<=n;++i){
- F[i-1][i][0]=F[i-1][i][1]=cst[i-1];
- G[i-1][1].update(1,1,n,i,F[i-1][i][1]+dist[i]+D[i]);
- G[i][0].update(1,1,n,i-1,F[i-1][i][0]+dist[i-1]+D[i-1]);
- H[i-1][1].update(1,1,n,i,F[i-1][i][1]-dist[i]+D[i]);
- H[i][0].update(1,1,n,i-1,F[i-1][i][0]-dist[i-1]+D[i-1]);
- }
- for(int len=2;len<=n;++len){
- for(int l=1;l+len<=n;++l){
- calc(l,l+len);
- }
- }
- printf("%lld\n",F[1][n][0]);
- }
- int main()
- {
- readin();
- work();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement