Submission #1099278

#TimeUsernameProblemLanguageResultExecution timeMemory
1099278tht2005Building Bridges (CEOI17_building)C++17
100 / 100
102 ms5920 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = (int)1e5 + 10; int h[N]; ll s[N], f[N]; struct line_t { ll k, m; ll operator() (ll x) { return k * x + m; } bool operator< (const line_t& rhs) const { if(k != rhs.k) return k > rhs.k; return m < rhs.m; } bool operator== (const line_t& rhs) const { return k == rhs.k; } }; struct cht { deque<line_t> dq; ll div(ll a, ll b) { // floored division return a / b - ((a ^ b) < 0 && a % b); } bool check(const line_t& a, const line_t& b, const line_t& c) { return div(b.m - a.m, a.k - b.k) >= div(c.m - b.m, b.k - c.k); } void add(const line_t& l) { while((int)dq.size() > 1 && check(dq[(int)dq.size() - 2], dq.back(), l)) dq.pop_back(); dq.push_back(l); } ll query(int x) { while((int)dq.size() > 1 && dq[0](x) >= dq[1](x)) dq.pop_front(); return dq.front()(x); } }; line_t lf[N]; int rt[N]; void dq(int l, int r) { if(l == r) return; int m = (l + r) >> 1; dq(l, m); for(int i = l; i <= m; ++i) lf[i] = { -2LL * h[i], f[i] + (ll)h[i] * h[i] - s[i] }; sort(lf + l, lf + m + 1); int ptr = unique(lf + l, lf + m + 1) - lf; cht c; for(int i = l; i < ptr; ++i) c.add(lf[i]); for(int i = m + 1; i <= r; ++i) rt[i] = i; sort(rt + m + 1, rt + r + 1, [&](int i, int j) { return h[i] < h[j]; }); for(int j = m + 1; j <= r; ++j) { int i = rt[j]; f[i] = min(f[i], c.query(h[i]) + (ll)h[i] * h[i] + s[i - 1]); } dq(m + 1, r); } int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; for(int i = 1; i <= n; ++i) cin >> h[i]; for(int i = 1; i <= n; ++i) { cin >> s[i]; s[i] += s[i - 1]; } memset(f, 0x3f, sizeof(f)); f[1] = 0; dq(1, n); cout << f[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...