제출 #66181

#제출 시각아이디문제언어결과실행 시간메모리
66181polyfishBuilding Bridges (CEOI17_building)C++14
0 / 100
89 ms28588 KiB
//I love armpit fetish #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "building" const int MAX_N = 100002; const int64_t INF = 1e18; struct line { int64_t a, b; line() {} line(int64_t a, int64_t b): a(a), b(b) {} int64_t get(int64_t x) { return a * x + b; } }; class IT { public: struct node { line d; node *left_child, *right_child; node() { d.a = 0; d.b = INF; left_child = NULL; right_child = NULL; } void make_children() { if (left_child==NULL) { left_child = new node(); right_child = new node(); } } }; int n; node *root; IT(int _n) { n = _n; root = new node(); } void upd(line val, int l, int r, node *cur) { if (l>r) return; int mid = (l + r) / 2; cur->make_children(); if (val.get(l)<=cur->d.get(l) && val.get(r)<=cur->d.get(r)) cur->d = val; else if (val.get(l)>=cur->d.get(l) && val.get(r)>=cur->d.get(r)) return; else if (val.get(l)>=cur->d.get(l) && val.get(mid)>=cur->d.get(mid)) upd(val, mid+1, r, cur->right_child); else if (val.get(l)<=cur->d.get(l) && val.get(mid)<=cur->d.get(mid)) { upd(cur->d, mid+1, r, cur->right_child); cur->d = val; } else if (val.get(r)>=cur->d.get(r) && val.get(mid)>=cur->d.get(mid)) upd(val, l, mid, cur->left_child); else if (val.get(r)<=cur->d.get(r) && val.get(mid)<=cur->d.get(mid)) { upd(cur->d, l, mid, cur->left_child); cur->d = val; } } int64_t get(int pos, int l, int r, node *cur) { if (pos<l || pos>r) return INF; cur->make_children(); int64_t res = cur->d.get(pos); if (l==r) return res; int mid = (l + r) / 2; return min(res, min(get(pos, l, mid, cur->left_child), get(pos, mid+1, r, cur->right_child))); } void upd(line val) { upd(val, 1, n, root); } int64_t get(int pos) { return get(pos, 1, n, root); } }; int n; int64_t h[MAX_N], w[MAX_N], f[MAX_N]; int64_t sqr(int64_t x) { return x * x; } void enter() { cin >> n; for (int i=1; i<=n; ++i) { cin >> h[i]; } for (int i=1; i<=n; ++i) { cin >> w[i]; w[i] += w[i-1]; } } void solve() { IT tr(*max_element(h+1, h+n+1)); tr.upd(line(-2*h[1], f[1] - w[1] + sqr(h[1]))); for (int i=2; i<=n; ++i) { f[i] = tr.get(h[i]) + w[i-1] + sqr(h[i]); tr.upd(line(-2*h[i], f[i] - w[i] + sqr(h[i]))); } cout << f[n]; } int main() { //#define OFFLINE_JUDGE doraemon #ifdef OFFLINE_JUDGE freopen(FILE_NAME".inp", "r", stdin); //freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); enter(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...