Submission #1015972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015972		thinknoexit	Building Bridges (CEOI17_building)	C++17	100 / 100	53 ms	23132 KiB

building

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;
ll h[100100], w[100100];
ll dp[100100];
ll qs[100100];
struct line {
    ll m, c;
    line() : m(0), c(4e18) {}
    line(ll m, ll c) : m(m), c(c) {}
    ll operator() (const ll& x) {
        return m * x + c;
    }
};
struct A {
    line w;
    A* l;
    A* r;
    A() : w(), l(nullptr), r(nullptr) {}
    A(ll m, ll c) : w(m, c), l(nullptr), r(nullptr) {}
};
using pA = A*;
pA root = new A();
void update(pA w, pA now = root, int l = 0, int r = 1000000) {
    bool cl = w->w(l) < now->w(l);
    bool cr = w->w(r) < now->w(r);
    if (!cl && !cr) return;
    if (cl && cr) {
        swap(now->w, w->w);
        return;
    }
    int mid = (l + r) >> 1;
    bool cm = w->w(mid) < now->w(mid);
    if (cm) {
        swap(now->w, w->w);
        if (!cl) update(w, now->l = (now->l) ? now->l : new A(), l, mid);
        else update(w, now->r = (now->r) ? now->r : new A(), mid, r);
    }
    else {
        if (cl) update(w, now->l = (now->l) ? now->l : new A(), l, mid);
        else update(w, now->r = (now->r) ? now->r : new A(), mid, r);
    }
}
ll query(int x, pA now = root, int l = 0, int r = 1000000) {
    if (l + 1 == r) return now->w(x);
    int mid = (l + r) >> 1;
    if (x < mid)
        return min(now->w(x), query(x, now->l = (now->l) ? now->l : new A(), l, mid));
    return min(now->w(x), query(x, now->r = (now->r) ? now->r : new A(), mid, r));
}
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> h[i];
    for (int i = 1;i <= n;i++) {
        cin >> w[i];
        qs[i] = qs[i - 1] + w[i];
    }
    // dp[i] = min(-2 * h[i] * h[j] + dp[j] - qs[j] + h[j] * h[j]) + qs[i-1] + h[i] * h[i]
    // m = -2 * h[j], c = dp[j] - qs[j] + h[j] * h[j]
    // x = h[i]
    dp[1] = 0;
    update(new A(-2 * h[1], dp[1] - qs[1] + h[1] * h[1]));
    for (int i = 2;i <= n;i++) {
        dp[i] = query(h[i]) + qs[i - 1] + h[i] * h[i];
        update(new A(-2 * h[i], dp[i] - qs[i] + h[i] * h[i]));
    }
    cout << dp[n];
    return 0;
}

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