Submission #1126477

#TimeUsernameProblemLanguageResultExecution timeMemory
1126477vladiliusBuilding Bridges (CEOI17_building)C++20
0 / 100
80 ms65352 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; #define pb push_back #define ff first #define ss second const ll inf = numeric_limits<ll> :: max(); struct DS{ struct line{ ll k, b; ll operator ()(int x){ return k * x + b; } }; vector<line> t; ll mn; int n; void init(){ mn = inf; n = 1e6; t.resize(4 * n); } void add(int v, int tl, int tr, line f){ if (tl == tr){ if (f(tl) < t[v](tl)){ t[v] = f; } return; } int tm = (tl + tr) / 2, vv = 2 * v; if (t[v].k > f.k) swap(f, t[v]); if (f(tm) < t[v](tm)){ swap(t[v], f); add(vv + 1, tm + 1, tr, f); } else { add(vv, tl, tm, f); } } void add(ll k, ll b){ line f = {k, b}; mn = min(mn, b); add(1, 1, n, f); } ll get(int v, int tl, int tr, int& x){ if (tl == tr) return t[v](x); int tm = (tl + tr) / 2, vv = 2 * v; if (x <= tm){ return min(t[v](x), get(vv, tl, tm, x)); } return min(t[v](x), get(vv + 1, tm + 1, tr, x)); } ll get(int x){ if (!x){ return mn; } return get(1, 1, n, x); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin>>n; vector<int> h(n + 1), w(n + 1); for (int i = 1; i <= n; i++){ cin>>h[i]; } vector<ll> p(n + 1); for (int i = 1; i <= n; i++){ cin>>w[i]; p[i] = p[i - 1] + w[i]; } auto sq = [&](int x){ return 1LL * x * x; }; vector<ll> dp(n + 1); DS T; T.init(); T.add(-2 * h[1], sq(h[1]) - w[1]); for (int i = 2; i <= n; i++){ dp[i] = (p[i - 1] + sq(h[i])) + T.get(h[i]); T.add(-2 * h[i], dp[i] - p[i] + sq(h[i])); } cout<<dp[n]<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...