Submission #132414

#TimeUsernameProblemLanguageResultExecution timeMemory
132414VardanyanBuilding Bridges (CEOI17_building)C++14
30 / 100
107 ms6772 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1000*100+5; long long dp[N]; long long a[N]; long long b[N]; long long pref[N]; const long long INF = 100000000000000; struct line{ long long k,b; line():k(0),b(0){} line(long long _k,long long _b):k(_k),b(_b){} }; long long f(line ln,long long x){ if(ln.k+ln.b == 0) return 1000000000000000000; return ln.k*x+ln.b; } struct node{ node* l; node* r; line ln; node():l(NULL),r(NULL),ln(0,0){} }; long long maxn = INF; void add_line(node* v,line ln,long long l = -maxn,long long r = maxn){ if(l>r) return; long long m = (l+r)/2; bool lef = f(ln,l)<f(v->ln,l); bool mid = f(ln,m)<f(v->ln,m); if(mid){ swap(v->ln,ln); } if(lef!=mid){ if(v->l == NULL) v->l = new node(); add_line(v->l,ln,l,m); } else{ if(v->r == NULL) v->r = new node(); add_line(v->r,ln,m+1,r); } } long long get(node* v,long long x,long long l = -maxn,long long r = maxn){ if(v == NULL || l>r) return 1000000000000000000; if(l == r){ return f(v->ln,x); } long long m = (l+r)/2; if(f(v->ln,x)<f(v->ln,m)){ return min(f(v->ln,x),get(v->l,x,l,m)); } else{ return min(f(v->ln,x),get(v->r,x,m+1,r)); } } int main(){ ios_base::sync_with_stdio(false); int n; cin>>n; for(int i = 1;i<=n;i++) cin>>a[i]; for(int i = 1;i<=n;i++){ cin>>b[i]; pref[i] = pref[i-1]+b[i]; // dp[i] = INF; } dp[1] = 0; node* root = new node(); add_line(root,line(a[1],dp[1]+a[1]*a[1]-pref[1])); for(int i = 2;i<=n;i++){ /*for(int j = 1;j<i;j++){ dp[i] = min(dp[i],dp[j]+(a[i]-a[j])*(a[i]-a[j])+pref[i-1]-pref[j]); }*/ long long x = get(root,-2*a[i]); dp[i] = x+a[i]*a[i]+pref[i-1]; add_line(root,line(a[i],dp[i]+a[i]*a[i]-pref[i])); // cout<<dp[i]<<endl; } cout<<dp[n]<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...