Submission #45431

#TimeUsernameProblemLanguageResultExecution timeMemory
45431Noam527Building Bridges (CEOI17_building)C++11
100 / 100
221 ms11684 KiB
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <string> #include <time.h> #include <stack> #include <queue> #include <random> #include <fstream> #define endl '\n' #define flush fflush(stdout), cout.flush() #define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define debug cout << "ok" << endl #define finish(x) return cout << x << endl, 0 typedef long long ll; typedef long double ldb; const int md = 1e9 + 7, inf = 1e9 + 7; const ll hs = 199; const ldb eps = 1e-9, pi = acos(-1); using namespace std; // assumes b1, b2 are nonzero bool smaller(ll t1, ll b1, ll t2, ll b2) { if (abs((ll)9e18 / b2) < t1 || abs((ll)9e18 / b1) < t2) return (ldb)t1 / b1 < (ldb)t2 / b2; if ((b1 > 0) == (b2 > 0)) return t1 * b2 < t2 * b1; return t1 * b2 > t2 * b1; } // 1 for maximum, -1 for minimum struct cht { struct line { ll m, b; bool q; ll nxtm, nxtb; line(ll mm = 0, ll bb = 0, bool qq = false) { m = mm; b = bb; q = qq; nxtm = nxtb = 9e18; } bool operator < (const line &x) const { if (!q && !x.q) return m < x.m; if (x.q) { // cout << "comparison with line " << -m << " " << -b << endl; if (nxtm == (ll)9e18) return false; // cout << "has next slope as " << nxtm << endl; // cout << (ldb)(b - nxtb) / (nxtm - m) << endl; return smaller(b - nxtb, nxtm - m, x.m, 1); } return !(x < *this); } }; int sign; set<line> h; cht(int type = 1) { sign = type; } void upd(set<line>::iterator &it) { if (next(it) == h.end()) return; line l1 = *it, l2 = *next(it); h.erase(it); l1.nxtm = l2.m, l1.nxtb = l2.b; it = h.insert(l1).first; } bool ok(set<line>::iterator &it) { // cout << "h" << endl; if (it == h.begin() || next(it) == h.end()) return true; // cout << "hm" << endl; auto it1 = prev(it), it2 = next(it); // cout << "hmm" << endl; bool rtn = smaller(it1->b - it->b, it->m - it1->m, it2->b - it->b, it->m - it2->m); // cout << "hmmm" << endl; if (!rtn) { // cout << "erasing " << sign * it->m << " " << sign * it->b << endl; h.erase(it); upd(it1); it = it1; // cout << "end erase" << endl; } return rtn; } void insert(ll constant, ll slope) { line l(sign * slope, sign * constant); auto pp = h.insert(l); set<line>::iterator it, it2; if (pp.second) it = pp.first; else { if (sign * pp.first->b <= sign * l.b) return; h.erase(pp.first); it = h.insert(l).first; } if (!ok(it)) return; upd(it); if (it != h.begin()) upd(--it), ++it; // debug; if (it != h.begin()) { while (!ok(it2 = prev(it))); } // debug; if (next(it) != h.end()) { while (!ok(it2 = next(it))) it = it2; } // debug; } ll query(ll x) { // cout << "looking for optimum on x " << x << endl; line l(x, 0, true); auto it = h.lower_bound(l); // cout << "optimum for x " << x << " is line "; // cout << sign * it->m << " " << sign * it->b << endl; return sign * (x * it->m + it->b); } }; int n; vector<ll> h, w, sw, dp; cht c(-1); int main() { fast; // freopen("C:\\Users\\Noam\\Desktop\\building.01.05.in", "r", stdin); cin >> n; h.resize(n); w.resize(n); sw.resize(n); dp.resize(n); for (auto &i : h) cin >> i; for (auto &i : w) cin >> i; sw[0] = w[0]; for (int i = 1; i < n; i++) sw[i] = sw[i - 1] + w[i]; dp[0] = 0; // cout << "for i " << 0 << " inserted " << dp[0] + h[0] * h[0] - sw[0] << " " << -2 * h[0] << endl; c.insert(dp[0] + h[0] * h[0] - sw[0], -2 * h[0]); for (int i = 1; i < n; i++) { dp[i] = c.query(h[i]) + sw[i - 1] + h[i] * h[i]; // cout << "for i " << i << " inserted " << -2 * h[i] << " " << dp[i] + h[i] * h[i] - sw[i] << endl; c.insert(dp[i] + h[i] * h[i] - sw[i], -2 * h[i]); } // for (int i = 0; i < n; i++) cout << dp[i] << " "; cout << endl; cout << dp.back() << endl; /* vector<ll> dp2(n); dp2[0] = 0; for (int i = 1; i < n; i++) { dp2[i] = 9e18; for (int j = 0; j < i; j++) dp2[i] = min(dp2[i], dp2[j] + (h[i] - h[j]) * (h[i] - h[j]) + sw[i - 1] - sw[j]); } cout << dp2.back() << endl; for (int i = 0; i < n; i++) { if (dp[i] != dp2[i]) { cout << "first difference at " << i << endl; cout << dp[i] << " " << dp2[i] << endl; return 0; } } */ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...