Submission #948214

#TimeUsernameProblemLanguageResultExecution timeMemory
948214amirhoseinfar1385Building Bridges (CEOI17_building)C++17
100 / 100
2985 ms8180 KiB
#include<bits/stdc++.h> using namespace std; const long long maxn=100000+10; long long inf=1e17; struct func{ long long x,y; func(){ x=inf; y=0; } long long get(long long w){ return x+w*y; } bool operator ==(func f){ return (f.x==x&&f.y==y); } }fakefunc; struct lichao{ struct node{ long long l,r; node(){ l=r=-1; } func f; }; node seg[maxn]; int te=1; int gor(int i){ if(seg[i].r==-1){ seg[i].r=te; te++; } return seg[i].r; } int gol(int i){ if(seg[i].l==-1){ seg[i].l=te; te++; } return seg[i].l; } void add(func f,long long i=0,long long l=-2e6,long long r=2e6){ if(l==r){ return ; } if(seg[i].f==fakefunc){ seg[i].f=f; return ; } long long m=(l+r)/2; if(seg[i].f.get(l)>f.get(l)){ swap(seg[i].f,f); } if(seg[i].f.get(m)<=f.get(m)){ add(f,gor(i),m,r); }else{ swap(seg[i].f,f); add(f,gol(i),l,m); } } long long pors(long long w,long long i=0,long long l=-2e6,long long r=2e6){ if(l==r){ return 0; } long long ret=seg[i].f.get(w); long long m=(l+r)>>1; if(w>=m&&seg[i].r!=-1){ ret=min(ret,pors(w,seg[i].r,m,r)); } if(w<m&&seg[i].l!=-1){ ret=min(ret,pors(w,seg[i].l,l,m)); } return ret; } }lich; long long dp[maxn],n,w[maxn],h[maxn],ps[maxn]; void vorod(){ cin>>n; for(long long i=1;i<=n;i++){ cin>>h[i]; } for(long long i=1;i<=n;i++){ cin>>w[i]; } for(long long i=1;i<=n;i++){ ps[i]=ps[i-1]+w[i]; } } void add(long long i){ func f; f.x=dp[i]-ps[i]+h[i]*h[i]; f.y=-2*h[i]; //cout<<"add: "<<f.x<<" "<<f.y<<endl; lich.add(f); } void upd(long long i){ dp[i]=+ps[i-1]+h[i]*h[i]+lich.pors(h[i]); //cout<<"upd: "<<dp[i]<<endl; } void solve(){ dp[1]=0; add(1); for(long long i=2;i<=n;i++){ upd(i); add(i); } } void khor(){ cout<<dp[n]<<endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); //cout.tie(0); //freopen("inp.txt","r",stdin); vorod(); solve(); khor(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...