Submission #1112156

#TimeUsernameProblemLanguageResultExecution timeMemory
1112156AvianshBuilding Bridges (CEOI17_building)C++17
30 / 100
3040 ms37316 KiB
#include <bits/stdc++.h> using namespace std; long long inf = 2e18; struct line{ long long m; long long c; double val(double x){ return m*x+c; } }; struct liChaoTree{ line *st; line def; int n; liChaoTree(int siz){ def.m=0; def.c=LLONG_MAX; int x = (int)ceil(log2(siz)); st=new line[(1<<(x+1))]; fill(st,st+(1<<(x+1)),def); n=siz; } void addLine(line lin, long long l=0, long long r=1000005, int ind=0){ long long mid = (l+r)/2; if(st[ind].val(l)<=lin.val(l)&&st[ind].val(r)<=lin.val(r)){ return; } if(st[ind].val(mid)>lin.val(mid)){ swap(lin,st[ind]); //cout << "set " << ind << " to " << st[ind].m << " " << st[ind].c << "\n"; } if(l==r) return; addLine(lin,l,mid,2*ind+1); addLine(lin,mid+1,r,2*ind+2); //cout << "added smth" << "\n"; } double query(long long x, long long l=0, long long r=1000005, int ind=0){ if(l==r&&r==x){ //cout << "got " << st[ind].val(x) << " from " << st[ind].m << " " << st[ind].c << "\n"; return st[ind].val(x); } if(x<l||x>r){ return def.val(x); } long long mid = (l+r)/2; return min({st[ind].val(x),query(x,l,mid,ind*2+1),query(x,mid+1,r,ind*2+2)}); } }; signed main(){ //ios::sync_with_stdio(0); //cin.tie(0); long long n; cin >> n; long long arr[n]; for(long long &i : arr){ cin >> i; } long long w[n]; for(long long &i : w){ cin >> i; } long long dp[n]; dp[0]=0; dp[1]=arr[0]*arr[0]+arr[1]*arr[1]-2*arr[0]*arr[1]; long long pref[n]; pref[0]=w[0]; for(int i = 1;i<n;i++){ pref[i]=pref[i-1]+w[i]; } liChaoTree lct(1000005); line l1,l2; l1.m=-2*arr[0]; l2.m=-2*arr[1]; l1.c=dp[0]-pref[0]+arr[0]*arr[0]; l2.c=dp[1]-pref[1]+arr[1]*arr[1]; //cout << "adding: \n"; lct.addLine(l1); lct.addLine(l2); for(long long i = 2;i<n;i++){ dp[i]=inf; //cout << dp[i] << " " << lct.query(arr[i]) << "\n"; dp[i]=lct.query(arr[i]); dp[i]+=pref[i-1]+arr[i]*arr[i]; line t; t.m=-2*arr[i]; t.c=dp[i]-pref[i]+arr[i]*arr[i]; lct.addLine(t); } cout << dp[n-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...