Submission #231660

#TimeUsernameProblemLanguageResultExecution timeMemory
231660kimbj0709Building Bridges (CEOI17_building)C++14
60 / 100
70 ms9740 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define maxn 100050 struct Line { int m, b; int operator()(int x) { return m * x + b; } } a[maxn*4]; void insert(int l, int r, Line seg, int o) { if(l + 1 == r) { if(seg(l) > a[o](l)) a[o] = seg; return; } int mid= (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2; if(a[o].m > seg.m) swap(a[o], seg); if(a[o](mid) < seg(mid)) { swap(a[o], seg); insert(l, mid, seg, lson); } else insert(mid, r, seg, rson); } int query(int l, int r, int x, int o) { if(l + 1 == r) return a[o](x); int mid = (l + r) >> 1, lson = o * 2 + 1, rson = o * 2 + 2; if(x < mid) return max(a[o](x), query(l, mid, x, lson)); else return max(a[o](x), query(mid, r, x, rson)); } int32_t main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); for(int i=0;i<maxn*4;i++){ a[i] = {(int)0,(int)(-10000000000000000)}; } int no_of_input; cin >> no_of_input; int input; int s = 0; vector<int> vect1; vector<int> vect2; vector<int> dp(no_of_input+1,0); for(int i=0;i<no_of_input;i++){ cin >> input; vect1.push_back(input); } for(int i=0;i<no_of_input;i++){ cin >> input; s += input; vect2.push_back(input); } s -= vect2[0]; vect2[0] = 0; dp[0] = 0; Line temp; temp.m = 2*vect1[0]; temp.b = -(vect1[0]*vect1[0]-vect2[0]); insert(0,maxn,temp,0); for(int i=1;i<no_of_input;i++){ //cout << query(0,maxn,vect1[i],0) << endl; assert(query(0,maxn,vect1[i],0)!=-10000000000000000); dp[i] = -query(0,maxn,vect1[i],0)-vect2[i]+vect1[i]*vect1[i]; Line temp; temp.m = 2*vect1[i]; temp.b = -(vect1[i]*vect1[i]+dp[i]); //cout << temp.m << " " << temp.b << endl; insert(0,maxn,temp,0); } /*for(int i=0;i<no_of_input;i++){ cout << dp[i] << ' '; } cout << endl;*/ cout << dp[no_of_input-1]+s; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...