Submission #1222026

#TimeUsernameProblemLanguageResultExecution timeMemory
1222026395333emBuilding Bridges (CEOI17_building)C++20
100 / 100
29 ms8712 KiB
#include <bits/stdc++.h> #define int long long #define emb emplace_back #define pii pair <int, int> using namespace std; const int mod = 1e9 + 7; const int inf = 1e18; const int N = 1e5 + 5; const int H = 1e6; int n, h[N], w[N], pref[N], dp[N]; struct line { int m, c; int cal(int x){ return m * x + c; } line(int m, int c) : m(m), c(c) {} }; struct lichaotree { struct node { line val; node *l, *r; node(line val) : l(0), r(0), val(val) {} }; typedef node* pnode; pnode root; void update(int l, int r, pnode &i, line curr){ if (!i) return i = new node(curr), void(); int mid = (l + r) / 2; if (curr.cal(mid) < i->val.cal(mid)) swap(curr, i->val); if (curr.cal(l) < i->val.cal(l)) update(l, mid, i->l, curr); if (curr.cal(r) < i->val.cal(r)) update(mid + 1, r, i->r, curr); } int query(int l, int r, pnode &i, int idx){ if (!i) return inf; if (l == r) return i->val.cal(idx); int mid = (l + r) / 2; if (idx <= mid) return min(i->val.cal(idx), query(l, mid, i->l, idx)); else return min(i->val.cal(idx), query(mid + 1, r, i->r, idx)); } } lct; signed main(){ cin.tie(NULL)->sync_with_stdio(false); cin >> n; for (int i = 1; i <= n; i++) cin >> h[i]; for (int i = 1; i <= n; i++) cin >> w[i], pref[i] = pref[i - 1] + w[i]; dp[1] = 0; for (int i = 2; i <= n; i++) dp[i] = inf; lct.update(1, H, lct.root, line(-2 * h[1], dp[1] + h[1] * h[1] - pref[1])); for (int i = 2; i <= n; i++) { dp[i] = pref[i - 1] + h[i] * h[i] + lct.query(1, H, lct.root, h[i]); lct.update(1, H, lct.root, line(-2 * h[i], dp[i] + h[i] * h[i] - pref[i])); } cout << dp[n]; } /* dp[i] = min(dp[i], dp[j] + pref[i - 1] - pref[j] + (h[i] - h[j]) * (h[i] - h[j])) = min(dp[i], dp[j] + pref[i - 1] - pref[j] + h[i]^2 - 2(h[i])(h[j]) + h[j]^2) = pref[i - 1] + h[i]^2 + min_element(dp[j] - pref[j] - 2(h[i])(h[j]) + h[j]^2) = pref[i - 1] + h[i]^2 + min_element(-2(h[i])(h[j]) + dp[j] - pref[j] + h[j]^2) from y = mx + c m = -2(h[j]) x = h[i] c = dp[j] + h[j]^2 - pref[j] */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...