Submission #469397

#	Time	Username	Problem	Language	Result	Execution time	Memory
469397		idk321	Building Bridges (CEOI17_building)	C++17	100 / 100	69 ms	8908 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 << i << " "<< dp[i] << endl;
    }

    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

/*
4
5 3 3 8
237401 12167 103925 160133
*/

/*
100
5 3 3 8 8 7 6 3 0 7 2 6 8 2 6 2 1 1 7 2 8 1 6 1 4 5 4 9 6 5 0 5 1 6 3 4 1 3 6 6 2 4 7 0 9 8 7 4 5 9 3 5 4 7 3 5 9 6 0 6 8 3 9 8 9 3 4 5 6 2 4 7 2 5 8 7 7 5 4 8 2 4 5 8 1 0 5 8 2 0 7 4 6 8 9 1 3 8 9 7
237401 12167 103925 160133 70604 218423 156382 107805 177948 112953 137895 52862 264805 160813 296652 123743 224582 255611 168282 299218 156579 210460 131634 211562 129285 25799 138253 123971 178024 100428 212637 94547 104591 39404 64233 33401 177293 184843 72746 248759 148945 103419 253608 80287 90674 79764 238107 259217 274476 116137 194955 269661 240069 250746 243559 292190 146947 281559 215155 125412 226065 19612 187175 31104 253324 107643 190631 233118 277562 218222 19936 274524 219379 168433 283571 236181 148888 254077 2697 98896 233594 24439 141225 92543 37541 17252 157010 86836 272477 271540 58929 284930 256641 256704 229314 76460 176504 157143 134504 222556
*/

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