Submission #826292

#TimeUsernameProblemLanguageResultExecution timeMemory
826292NK_Building Bridges (CEOI17_building)C++17
100 / 100
41 ms8128 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define mp make_pair #define f first #define s second #define sz(x) int(x.size()) template<class T> using V = vector<T>; using vi = V<int>; using ll = long long; using pl = pair<ll, ll>; using vl = V<ll>; // using vpi = V<pi>; const ll INFL = ll(1e18) + 1008; const int nax = int(1e6); struct line { ll m, b; line() { m = 0, b = INFL; } line(ll m, ll b) : m(m), b(b) { } ll get(ll x) { return m * x + b; } }; struct LiChao { struct node { node *l, *r; line x; node(line x) : x(x) { l = r = 0; } }; node *t = new node(line()); void upd(line x, node *&v, int l = 0, int r = nax) { if (!v) { v = new node(x); return; } // cout << l << " <-> " << r << endl; int m = (l + r) / 2; bool lf = x.get(l) < v->x.get(l); bool md = x.get(m) < v->x.get(m); if (md) swap(x, v->x); if (l == r) return; if (lf != md) upd(x, v->l, l, m); else upd(x, v->r, m+1, r); } ll get(int x, node *&v, int l = 0, int r = nax) { if (!v) return INFL; // cout << l << " < - > " << r << endl; int m = (l + r) / 2; if (l == r) return v->x.get(x); if (x < m) return min(v->x.get(x), get(x, v->l, l, m)); else return min(v->x.get(x), get(x, v->r, m+1, r)); } void upd(line x) { return upd(x, t); } ll get(int x) { return get(x, t); } }; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; vi A(N); for(auto& x : A) cin >> x; vi W(N); for(auto& x : W) cin >> x; if (A.front() > A.back()) { reverse(begin(A), end(A)); reverse(begin(W), end(W)); } vl P = {0}; for(auto& x : W) P.pb(P.back() + x); auto sq = [&](int x) { return x * 1LL * x; }; vl dp(N, INFL); dp[0] = 0; LiChao T; T.upd(line(-2 * A[0], dp[0] + sq(A[0]) - P[1])); for(int i = 1; i < N; i++) { dp[i] = T.get(A[i]) + sq(A[i]) + P[i]; T.upd(line(-2 * A[i], dp[i] + sq(A[i]) - P[i + 1])); } cout << dp.back() << nl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...