Submission #45956

#TimeUsernameProblemLanguageResultExecution timeMemory
45956sorry_BenqBuilding Bridges (CEOI17_building)C++17
100 / 100
123 ms18292 KiB
#pragma GCC optimize("O3") #pragma GCC target("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> pii; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() int w[100005]; ll h[100005]; ll dp[100005]; ll res = 0; bool Q; struct Line { mutable ll k, m, p; // slope, y-intercept, last optimal x bool operator<(const Line& o) const { return Q ? p < o.p : k < o.k; } }; struct LineContainer : multiset<Line> { const ll inf = LLONG_MAX; ll div(ll a, ll b) { // floored division if (b < 0) a *= -1, b *= -1; if (a >= 0) return a/b; return -((-a+b-1)/b); } // updates x->p, determines if y is unneeded bool isect(iterator x, iterator y) { if (y == end()) { x->p = inf; return 0; } if (x->k == y->k) x->p = x->m > y->m ? inf : -inf; else x->p = div(y->m - x->m, x->k - y->k); return x->p >= y->p; } void add(ll k, ll m) { auto z = insert({k, m, 0}), y = z++, x = y; while (isect(y, z)) z = erase(z); if (x != begin() && isect(--x, y)) isect(x, y = erase(y)); while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y)); } ll query(ll x) { // gives max value assert(!empty()); Q = 1; auto l = *lb({0,0,x}); Q = 0; return l.k * x + l.m; } }; int main(){ LineContainer L; int N; cin >> N; for (int i = 0; i < N; i++){ cin >> h[i]; } for (int i = 0; i < N; i++){ cin >> w[i]; res += w[i]; w[i] = -w[i]; } dp[0] = w[0]; L.add(2*h[0], -h[0]*h[0] - dp[0]); for (int i = 1; i < N; i++){ dp[i] = h[i]*h[i] + w[i] - L.query(h[i]); L.add(2*h[i], -h[i]*h[i] - dp[i]); } cout << res + dp[N - 1] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...