oj.uz

Submission #469397

# Submission time Handle Problem Language Result Execution time Memory
469397 2021-08-31T20:03:36 Z idk321 Building Bridges (CEOI17_building) C++17
100 / 100
 69 ms 8908 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2696 KB Output is correct
2 Correct 69 ms 2656 KB Output is correct
3 Correct 47 ms 2900 KB Output is correct
4 Correct 41 ms 2652 KB Output is correct
5 Correct 45 ms 3780 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 55 ms 2696 KB Output is correct
7 Correct 69 ms 2656 KB Output is correct
8 Correct 47 ms 2900 KB Output is correct
9 Correct 41 ms 2652 KB Output is correct
10 Correct 45 ms 3780 KB Output is correct
11 Correct 43 ms 2652 KB Output is correct
12 Correct 45 ms 2660 KB Output is correct
13 Correct 35 ms 2640 KB Output is correct
14 Correct 45 ms 2656 KB Output is correct
15 Correct 64 ms 8908 KB Output is correct
16 Correct 42 ms 3800 KB Output is correct
17 Correct 25 ms 2680 KB Output is correct
18 Correct 31 ms 2640 KB Output is correct