Submission #1205808

#TimeUsernameProblemLanguageResultExecution timeMemory
1205808friendiksBuilding Bridges (CEOI17_building)C++20
100 / 100
50 ms10824 KiB
#ifndef LOCAL #pragma GCC optimize("O3") #pragma GCC diagnostic ignored "-Wpedantic" #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; auto seed = chrono::high_resolution_clock::now().time_since_epoch().count(); mt19937 rnd(seed); template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T, typename V> using table = gp_hash_table<T, V>; using i128 = __int128; using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; const ll INF = 1e18; const int inf = 2e9; const int MOD = 998244353; const int maxn = 1e5 + 52; const ld pi = acos(-1); const int P = 5167; const int L = 26; template <typename T, typename V> void fill(T& container, V value) { for (auto& c : container) c = value; } #define int ll int k[4 * maxn], b[4 * maxn], x[maxn]; void build(int v, int l, int r) { k[v] = 0; b[v] = INF; if (l + 1 == r) return; int m = (r + l) / 2; build(v * 2 + 1, l, m); build(v * 2 + 2, m, r); } void add(int v, int l, int r, int K, int B) { if (k[v] == K) { b[v] = min(b[v], B); return; } int m = (r + l) / 2; if (k[v] * x[m] + b[v] > K * x[m] + B) { swap(k[v], K); swap(b[v], B); } if (l + 1 == r) return; if (k[v] > K) { add(v * 2 + 2, m, r, K, B); } else { add(v * 2 + 1, l, m, K, B); } } int get(int v, int l, int r, int i) { if (i < l || r <= i) return INF; if (l + 1 == r) return k[v] * x[i] + b[v]; int m = (r + l) / 2; return min({k[v] * x[i] + b[v], get(v * 2 + 1, l, m, i), get(v * 2 + 2, m, r, i)}); } void solve() { int n; cin >> n; vector<int> h(n), w(n); vector<pair<int, int>> v(n); for (int i = 0; i < n; ++i) { cin >> h[i]; v[i] = {h[i], i}; } for (int i = 0; i < n; ++i) cin >> w[i]; sort(v.begin(), v.end()); vector<int> pos(n); for (int i = 0; i < n; ++i) { x[i] = v[i].first; pos[v[i].second] = i; } build(0, 0, n); vector<int> p(n + 1); for (int i = 0; i < n; ++i) p[i + 1] = p[i] + w[i]; vector<int> dp(n); for (int i = 0; i < n; ++i) { int d = 0; if (i > 0) { dp[i] = h[i] * h[i] + p[i] + get(0, 0, n, pos[i]); d = dp[i]; } add(0, 0, n, -2 * h[i], h[i] * h[i] + d - p[i + 1]); } cout << dp[n - 1]; } signed main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(6); int t = 1; //cin >> t; while (t--) solve(); //stress(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...