Submission #1169866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169866		MinhKien	Building Bridges (CEOI17_building)	C++20	100 / 100	42 ms	18368 KiB

building

#include <iostream>

using namespace std;

#define ll long long
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const ll INF = 1e18;

int n;
ll h[N], w[N], dp[N];

struct lichao {
    struct line {
        ll a, b;

        line() {a = 0, b = INF;}
        line(ll A, ll B) {a = A, b = B;}
        ll calc(ll val) {return a * val + b;}
        ll slope() {return a;}
    } tr[M];

    void update(int l, int r, line f) {
        if (l > r) return;
        int m = (l + r) >> 1;

        if (l == r) {
            tr[m] = (f.calc(m) < tr[m].calc(m) ? f : tr[m]);
            return;
        }

        if (f.calc(m) < tr[m].calc(m)) swap(f, tr[m]);

        if (f.slope() > tr[m].slope()) {
            update(l, m - 1, f);
        }

        if (f.slope() < tr[m].slope()) {
            update(m + 1, r, f);
        }
    }

    ll get(int l, int r, int u) {
        int m = (l + r) >> 1;
        ll cur = tr[m].calc(u);
        if (u == m) return cur;
        if (u < m) return min(cur, get(l, m - 1, u));
        return min(cur, get(m + 1, r, u));
    }
} Tree;

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

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

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

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    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];
    }

    dp[1] = 0;
    Tree.update(0, 1e6, lichao::line(p1(1), p2(1)));
    for (int i = 2; i <= n; ++i) {
        dp[i] = Tree.get(0, 1e6, h[i]) + p3(i);
        Tree.update(0, 1e6, lichao::line(p1(i), p2(i)));
    }

    cout << dp[n] << "\n";

    return 0;
}

// 6 
// 3 8 7 1 6 6
// 0 -1 9 1 2 0

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