Advertisement
Guest User

Untitled

a guest
May 6th, 2022
225
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.91 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. #include<vector>
  6. #include<algorithm>
  7. #include<set>
  8. #include<map>
  9. #include<queue>
  10.  
  11. #define ls(x) (x<<1)
  12. #define rs(x) (x<<1|1)
  13. #define pb push_back
  14. #define MP make_pair
  15.  
  16. using namespace std;
  17.  
  18. typedef long long LL;
  19.  
  20. const int maxn=3005;
  21. const int maxm=8205;
  22. const LL INF=100000000000000;
  23.  
  24. int n;
  25. LL dist[maxn];
  26. int D[maxn],cst[maxn];
  27. int pt[maxn];
  28.  
  29. LL F[maxn][maxn][2];
  30.  
  31. struct Seg{
  32. LL mi[maxm];
  33.  
  34. void pushup(int x)
  35. {
  36. mi[x]=min(mi[ls(x)],mi[rs(x)]);
  37. }
  38. void build(int x,int l,int r)
  39. {
  40. mi[x]=INF;
  41. if(l==r)
  42. return;
  43. int mid=(l+r)>>1;
  44. build(ls(x),l,mid),build(rs(x),mid+1,r);
  45. pushup(x);
  46. }
  47.  
  48. void update(int x,int l,int r,int pos,LL k)
  49. {
  50. if(l==r){
  51. mi[x]=k;
  52. return;
  53. }
  54. int mid=(l+r)>>1;
  55. if(pos<=mid)
  56. update(ls(x),l,mid,pos,k);
  57. else
  58. update(rs(x),mid+1,r,pos,k);
  59. pushup(x);
  60. }
  61.  
  62. LL query(int x,int l,int r,int ql,int qr)
  63. {
  64. if(r<ql||l>qr)
  65. return INF;
  66. if(l>=ql&&r<=qr)
  67. return mi[x];
  68. int mid=(l+r)>>1;
  69. return min(query(ls(x),l,mid,ql,qr),query(rs(x),mid+1,r,ql,qr));
  70. }
  71. }G[maxn][2],H[maxn][2];
  72.  
  73. void readin()
  74. {
  75. scanf("%d",&n);
  76. for(int i=3;i<=n+1;++i)
  77. scanf("%lld",&dist[i]),dist[i]+=dist[i-1];
  78. for(int i=2;i<=n+1;++i)
  79. scanf("%d",&D[i]);
  80. for(int i=1;i<=n+1;++i)
  81. scanf("%d",&cst[i]);
  82. n+=2;
  83. dist[n]=dist[n-1];
  84. }
  85.  
  86. void update_pt(int l,int r)
  87. {
  88. while(pt[l]<r-1){
  89. if(F[l][pt[l]][1]>=F[pt[l]][r][0])
  90. break;
  91. ++pt[l];
  92. }
  93. }
  94.  
  95. inline LL max(LL x,LL y)
  96. {
  97. return x>y?x:y;
  98. }
  99.  
  100. inline LL min(LL x,LL y)
  101. {
  102. return x<y?x:y;
  103. }
  104.  
  105. void calc(int l,int r)
  106. {
  107. update_pt(l,r);
  108. int pos=pt[l];
  109. F[l][r][0]=F[l][r][1]=INF;
  110. if(F[l][pos][1]>=F[pos][r][0]){
  111. F[l][r][0]=min(F[l][r][0],G[l][1].query(1,1,n,pos,r-1)-dist[l]);
  112. F[l][r][1]=min(F[l][r][1],H[l][1].query(1,1,n,pos,r-1)+dist[r]);
  113. }
  114. if(F[l][pos][1]<F[pos][r][0])
  115. ++pos;
  116. if(pos>l+1){
  117. F[l][r][0]=min(F[l][r][0],G[r][0].query(1,1,n,l+1,pos-1)-dist[l]);
  118. F[l][r][1]=min(F[l][r][1],H[r][0].query(1,1,n,l+1,pos-1)+dist[r]);
  119. }
  120.  
  121. G[l][1].update(1,1,n,r,F[l][r][1]+dist[r]+D[r]);
  122. G[r][0].update(1,1,n,l,F[l][r][0]+dist[l]+D[l]);
  123. H[l][1].update(1,1,n,r,F[l][r][1]-dist[r]+D[r]);
  124. H[r][0].update(1,1,n,l,F[l][r][0]-dist[l]+D[l]);
  125. }
  126.  
  127. void init()
  128. {
  129. for(int i=1;i<=n;++i){
  130. pt[i]=i+1;
  131. for(int j=0;j<=1;++j)
  132. G[i][j].build(1,1,n),H[i][j].build(1,1,n);
  133.  
  134. }
  135. }
  136.  
  137. void work()
  138. {
  139. init();
  140.  
  141. for(int i=2;i<=n;++i){
  142. F[i-1][i][0]=F[i-1][i][1]=cst[i-1];
  143. G[i-1][1].update(1,1,n,i,F[i-1][i][1]+dist[i]+D[i]);
  144. G[i][0].update(1,1,n,i-1,F[i-1][i][0]+dist[i-1]+D[i-1]);
  145. H[i-1][1].update(1,1,n,i,F[i-1][i][1]-dist[i]+D[i]);
  146. H[i][0].update(1,1,n,i-1,F[i-1][i][0]-dist[i-1]+D[i-1]);
  147. }
  148.  
  149. for(int len=2;len<=n;++len){
  150. for(int l=1;l+len<=n;++l){
  151. calc(l,l+len);
  152. }
  153. }
  154. printf("%lld\n",F[1][n][0]);
  155. }
  156.  
  157. int main()
  158. {
  159. readin();
  160. work();
  161. return 0;
  162. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement