Submission #882008

#	Time	Username	Problem	Language	Result	Execution time	Memory
882008		_callmelucian	Building Bridges (CEOI17_building)	C++14	100 / 100	62 ms	71260 KiB

building

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(v) v.begin(), v.end()

struct line {
    ll slope, c;
    line (ll u = 0, ll v = 0) : slope(u), c(v) {}
    ll calc (ll x) {return slope * x + c;}
};

struct liChao {
    vector<line> tr;
    liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)) {}

    void update (int k, line seg, int l, int r) {
        if (l + 1 == r) {
            if (seg.calc(l) < tr[k].calc(l)) tr[k] = seg;
            return;
        }
        int mid = (l + r) / 2;
        if (seg.slope > tr[k].slope) swap(seg, tr[k]); // seg must have lower slope
        if (seg.calc(mid) < tr[k].calc(mid)) {
            update(2 * k, tr[k], l, mid);
            tr[k] = seg;
        }
        else update(2 * k + 1, seg, mid, r);
    }

    ll query (int pos, int k, int l, int r) {
        if (l + 1 == r) return tr[k].calc(pos);
        int mid = (l + r) / 2;
        if (pos < mid) return min(tr[k].calc(pos), query(pos, 2 * k, l, mid));
        return min(tr[k].calc(pos), query(pos, 2 * k + 1, mid, r));
    }
};

const int M = 1e6 + 1;
ll dp[M], h[M], w[M];

ll f1 (int k) {
    return -2 * h[k];
}

ll f2 (int k) {
    return dp[k] + h[k] * h[k] - w[k];
}

ll f3 (int k) {
    return h[k] * h[k] + w[k - 1];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i] += w[i - 1];
    }

    liChao tree(M);
    tree.update(1, line(f1(1), f2(1)), 0, M);

    for (int i = 2; i <= n; i++) {
        dp[i] = tree.query(h[i], 1, 0, M) + f3(i);
        tree.update(1, line(f1(i), f2(i)), 0, M);
    }
    cout << dp[n];

    return 0;
}

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