Submission #1034396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034396		Blagoj	Building Bridges (CEOI17_building)	C++17	100 / 100	95 ms	129904 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) x.begin(), x.end()

const int mxn = 1e5 + 100;

vector<ll> h(mxn), val(mxn), prf(mxn);

ll sum(int l, int r) {
    return prf[r] - (l == 0 ? 0 : prf[l - 1]);
}

struct Node {
    ll m = 0, b = 1e16;
};

ll f(Node a, ll x) {
    return -a.m * x + a.b;
}

struct LiChao {
    vector<Node> sgt;

    LiChao(int sz) {
        sgt.resize(4 * sz);
    }

    void update(int k, int l, int r, Node nv) {
        int mid = (l + r) / 2;
        bool f1 = f(nv, l) < f(sgt[k], l);
        bool f2 = f(nv, mid) < f(sgt[k], mid);
        if (f2) swap(nv, sgt[k]);
        if (l == r) return;
        if (f1 != f2) update(k * 2, l, mid, nv);
        else update(k * 2 + 1, mid + 1, r, nv);
    }

    ll get(int k, int l, int r, ll x) {
        if (l > x || r < x) return 1e16;
        ll ans = f(sgt[k], x);
        if (l == r) return ans;
        int mid = (l + r) / 2;
        return min({ans, get(k * 2, l, mid, x), get(k * 2 + 1, mid + 1, r, x)});
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> h[i];
    for (int i = 0; i < n; i++) cin >> val[i];
    prf[0] = val[0];
    for (int i = 1; i < n; i++) prf[i] = prf[i - 1] + val[i];
    LiChao lc(2e6 + 100);
    lc.update(1, 0, 2e6, {2 * h[0], h[0] * h[0] - val[0]});
    ll ans[n];
    for (int i = 1; i < n; i++) {
        ll best = lc.get(1, 0, 2e6, h[i]) - val[i] + h[i] * h[i];
        ans[i] = best;
        lc.update(1, 0, 2e6, {2 * h[i], best + h[i] * h[i]});
    }
    cout << ans[n - 1] + sum(0, n - 1);
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40