Submission #1125235

#TimeUsernameProblemLanguageResultExecution timeMemory
1125235yusufhocaogluBuilding Bridges (CEOI17_building)C++20
0 / 100
80 ms32836 KiB
#include <iostream> #include <bits/stdc++.h> using namespace std; #define MOD 1000000007 #define MOD2 998244353 #define ll long long #define pri pair<int,int> #define prl pair<ll,ll> #define vi vector<int> #define vl vector<ll> #define vp vector<pair<int,int>> #define vpl vector<pair<ll,ll>> #define re return 0 #define sqrt sqrtl vi h;int n; struct Line { int a,b; Line() {} Line(int a,int b) : a(a),b(b) {} int operator()(int x) {return a*x+b;} }; vector<Line> seg; struct lichao { void insert(int i,Line ln,int l,int r) { if (l+1==r) { if (ln(l)<seg[i](l)) seg[i] = ln; return; } int m = (l+r)/2; if (ln.a > seg[i].a) swap(seg[i],ln); if (ln(m) < seg[i](m)) { //seg has higher slope and higher answer, so seg will always be better in right subtree swap(seg[i],ln); insert(2*i,ln,l,m); } else { //seg has higher slope but lower answer, ln should be in this node, and seg should be on the right subtree insert(2*i+1,ln,m,r); } } int query(int x,int i,int l,int r) { //cout<<"checking "<<x<<" for "<<seg[i].a<<" "<<seg[i].b<<endl; if (l+1==r) return seg[i](x); int m = (l+r)/2; if (x>m) return min(seg[i](x),query(x,2*i+1,m,r)); return min(seg[i](x),query(x,2*i,l,m)); } }; int32_t main() { cin>>n; h = vi(n); vi w(n); vi p(n+1); for (int i = 0;i<n;i++) cin>>h[i]; for (int i = 0;i<n;i++) { cin>>w[i]; p[i+1] = p[i]+w[i]; } //cout<<"yo nigga"<<endl; //prefix is 1-indexed int N = 1e6+2; seg = vector<Line>(4*N+1,Line(0,1e9)); lichao lct; int ans; lct.insert(1,Line(-2*h[0],-p[1]+h[0]*h[0]),0,N); for (int i = 1;i<n;i++) { ans = lct.query(h[i],1,0,N)+p[i]+h[i]*h[i]; //cout<<"query for "<<h[i]<<" is "<<ans<<endl; lct.insert(1,Line(-2*h[i],ans+h[i]*h[i]-p[i+1]),0,N); //cout<<"adding line: "<<-2*h[i]<<"x + "<<ans+h[i]*h[i]-p[i+1]<<endl; } //cout<<seg[1].a<<" "<<seg[1].b<<endl; cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...