Submission #129519

#TimeUsernameProblemLanguageResultExecution timeMemory
129519semiautoBuilding Bridges (CEOI17_building)C++14
100 / 100
172 ms35944 KiB
#include <bits/stdc++.h> using namespace std; const long long N=1024*1024,inf=N*N*N; long long n,i,sum; long long s[N],h[N]; pair <long long,long long> tree[2*N]; long long val(pair <long long,long long> line,long long x) { return x*line.first+line.second; } long long solve(long long x) { long long pos=x+N,ret=inf; while (pos) { ret=min(ret,val(tree[pos],x)); pos/=2; } return ret; } void add_line(pair <long long,long long> line,long long p,long long l,long long r) { long long m=(l+r)/2; bool lef=val(line,l-N)<val(tree[p],l-N); bool mid=val(line,m-N)<val(tree[p],m-N); if (mid) swap(tree[p],line); if (p<N) { if (lef!=mid) add_line(line,2*p,l,m); else add_line(line,2*p+1,m,r); } return; } int main() { cin>>n; for (i=1;i<=n;i++) cin>>h[i]; for (i=1;i<=n;i++) { cin>>s[i]; sum+=s[i]; } for (i=1;i<(2*N);i++) tree[i]={-2*h[1],h[1]*h[1]-s[1]}; for (i=2;i<n;i++) add_line({-2*h[i],2*h[i]*h[i]-s[i]+solve(h[i])},1,N,2*N); cout<<solve(h[n])+sum+h[n]*h[n]-s[n]<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...