Submission #503735

#TimeUsernameProblemLanguageResultExecution timeMemory
503735fvogel499Building Bridges (CEOI17_building)C++17
100 / 100
51 ms36664 KiB
/* * File created on 01/08/2022 at 19:13:29. * Link to problem: * Description: * Time complexity: O() * Space complexity: O() * Status: --- * Copyright: Ⓒ 2022 Francois Vogel */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> using namespace std; using namespace __gnu_pbds; #define pii pair<int, int> #define f first #define s second #define vi vector<int> #define all(x) x.begin(), x.end() #define size(x) (int)((x).size()) #define pb push_back #define ins insert #define cls clear #define int ll #define ll long long #define ld long double typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int p2 = 1<<20; const int inf = 1e18; struct LiChao { LiChao() { t = new pii [p2*2]; for (int i = 0; i < p2*2; i++) t[i] = pii(0, inf); } void update(pii v, int x = 1, int b = 0, int e = p2-1) { int m = (b+e)/2; if (t[x].f*m+t[x].s > v.f*m+v.s) swap(t[x], v); if (b < e) { if (v.f > t[x].f) { update(v, x*2, b, m); } else { update(v, x*2+1, m+1, e); } } } int get(int x) { int r = inf; for (int i = p2+x; i; i /= 2) r = min(r, t[i].f*x+t[i].s); return r; } pii* t; }; signed main() { cin.tie(0); ios_base::sync_with_stdio(0); int n; cin >> n; int b [n]; for (int i = 0; i < n; i++) cin >> b[i]; int w [n]; for (int i = 0; i < n; i++) cin >> w[i]; LiChao lc = LiChao(); int dp [n]; for (int i = n-1; i >= 0; i--) { dp[i] = lc.get(b[i]); if (i == n-1) dp[i] = 0; dp[i] += 2*b[i]*b[i]; dp[i] -= w[i]; lc.update(pii(-2*b[i], dp[i])); } int res = dp[0]-b[0]*b[0]-b[n-1]*b[n-1]; for (int i : w) res += i; cout << res; cout.flush(); int d = 0; d++; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...