Submission #597586

#TimeUsernameProblemLanguageResultExecution timeMemory
597586OttoTheDinoBuilding Bridges (CEOI17_building)C++17
100 / 100
103 ms16872 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,s,e) for (int i = s; i <= e; ++i) #define rrep(i,s,e) for (int i = s; i >= e; --i) #define pb push_back #define pf push_front #define fi first #define se second #define all(a) a.begin(), a.end() #define len(a) (int)a.size() typedef long long ll; typedef pair<int, int> ii; typedef pair<ll, ll> pll; typedef vector<ii> vii; typedef vector<int> vi; typedef vector<double> vd; typedef vector<string> vs; typedef vector<ll> vll; //let's implement cht then :))))))))) const ll inf = 1e9; ll cdiv (ll a, ll b) { return a / b + !(((a < 0) != (b < 0)) || !(a % b)); } int main() { ios::sync_with_stdio(0); cin.tie(0); ll n, s = 0; cin >> n; ll h[n+1], w[n+1], x[n+1], dp[n+1]; set<pll,greater<pll>> stk; set<pll> stx; rep (i,1,n) cin >> h[i]; rep (i,1,n) { cin >> w[i]; s += w[i]; } dp[1] = h[1]*h[1] - w[1]; stk.insert({-2*h[1],1}); stx.insert({-inf,1}); x[1] = -inf; rep (i,2,n) { auto iti = stx.upper_bound({h[i], inf}); --iti; ll u = (*iti).se; dp[i] = dp[u] + -2*h[u]*h[i] + h[i] * h[i] - w[i]; if (i==n) cout << s+dp[n] << "\n"; else { //add an element to the cht dp[i] += h[i]*h[i]; auto it = stk.upper_bound({-2*h[i], -inf}); bool beg = 0; if (it!=stk.begin()) { --it; while (true) { if ((*it).fi==-2*h[i]) { if (dp[i] >= dp[(*it).se]) break; } else { ll nx = cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi); if (nx>x[(*it).se]) break; } stx.erase({x[(*it).se], (*it).se}); it = stk.erase(it); if (it==stk.begin()) { beg = 1; break; } --it; } } else beg = 1; if (beg) { stk.insert({-2*h[i], i}); x[i] = -inf; stx.insert({-inf, i}); } else { if ((*it).fi==-2*h[i]) continue; int X = cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi); ++it; if (it==stk.end() || X <= x[(*it).se]) { if (it!=stk.end() && X==x[(*it).se]) { if (cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi)<=X) continue; } stx.insert({X, i}); stk.insert({-2*h[i],i}); x[i] = X; } else continue; } while (true) { if (it==stk.end()) break; int X = cdiv(dp[(*it).se]-dp[i],-2*h[i]-(*it).fi); ++it; if (it==stk.end()) { --it; stx.erase({x[(*it).se], (*it).se}); stx.insert({X, (*it).se}); x[(*it).se] = X; break; } if (X >= x[(*it).se]) { --it; stx.erase({x[(*it).se], (*it).se}); it = stk.erase(it); } else { --it; stx.erase({x[(*it).se], (*it).se}); stx.insert({X, (*it).se}); x[(*it).se] = X; break; } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...