Submission #469366

#	Time	Username	Problem	Language	Result	Execution time	Memory
469366		idk321	Building Bridges (CEOI17_building)	C++17	0 / 100	46 ms	2632 KiB

building

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

const ll INF = 1000000000000000006LL;

struct Line {
    mutable ll k, m, p;
    bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer {
    multiset<Line, less<>> sett;

    ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b);
    }

    bool isect(multiset<Line, less<>>::iterator x, multiset<Line, less<>>::iterator y) {
        if (y == sett.end()) {
            x->p = INF;
            return false;
        }
        if (x->k == y->k) {
            if (x->m > y->m) {
                x->p = -INF;
            } else x->p = INF;
        } else {
            x->p = div(x->m - y->m, y->k - x->k);
        }
        return x->p >= y->p;
    }

    void add(ll k, ll m) {
        auto z = sett.insert({k, m, 0});
        auto y = z;
        auto x = y;
        z++;
        while (isect(y, z)) z = sett.erase(z);
        if (x != sett.begin() && isect(--x, y)) isect(x, y = sett.erase(y));
        while ((y = x) != sett.begin() && (--x)->p >= y->p ) {
            isect(x, sett.erase(y));
        }
    }

    ll query(ll x) {
        assert(!sett.empty());
        auto l = *sett.lower_bound(x);
        return l.k * x + l.m;
    }
};

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

    int n;
    cin >> n;
    vector<ll> h(n);
    for (int i = 0; i < n; i++) cin >> h[i];
    vector<ll> w(n);
    for (int i = 0; i < n; i++) cin >> w[i];
    ll sum = 0;
    for (int i = 0; i < n; i++) sum += w[i];

    LineContainer lc;
    vector<ll> dp(n);
    for (int i = 0; i < n; i++) {
        dp[i] -= w[i];
        if (i != 0) {
            dp[i] -= lc.query(h[i]);
            dp[i] += h[i] * h[i];
        }

        lc.add(2 * h[i], -h[i] * h[i] - dp[i]);
    }

    cout << (dp[n - 1] + sum) << "\n";

}

/*
10
3 8 7 1 6 6 9 1 4 15
0 -1 9 1 2 0 5 3 2 10
*/
/*
-11 13 12 10 17 17
*/

//-31 -7 -8 -10 -3 -3 7 7 10 63

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

//0 26 7 3 6 6 6 0 -1 32

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