Submission #1122227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122227		_callmelucian	Building Bridges (CEOI17_building)	C++14	0 / 100	3057 ms	3040 KiB

building

// Massive thanks to Monarchuwu and VNOI for
// the wonderful blog about line-container (coming soon)

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const ld oo = 1e7;

struct line {
    ll slope, c;
    mutable ld p;

    line() : slope(0), c(0), p(-oo) {}
    line (ll u, ll v) : slope(u), c(v), p(-oo) {}

    ll calc (ll x) const { return slope * x + c; }

    bool operator < (const line &o) const { return slope > o.slope; }
    bool operator < (ll x) const { return p < x; }
};

struct lineContainer : multiset<line, less<void>> { // use less<void> to allow multiple comparator
    ld xSect (auto x, auto y) {
        if (x->slope == y->slope) {
            while (true);
        }
        return (ld) (y->c - x->c) / (x->slope - y->slope);
    }

    bool mustKeep (auto x, auto y) {
        // return true if we must keep y and update x->p accordingly
        // note that x->p at the beginning of the function is not correct
        if (y == end()) return x->p = oo, 1;
        if (x->slope == y->slope) { // edge case: parallel
            if (x->c < y->c) return 1;
        }
        return ((x->p = xSect(x, y)) < y-> p);
    }

    void add (ll slope, ll c) {
        // remove lines after x
        auto x = emplace(slope, c), y = next(x);
        while (!mustKeep(x, y)) y = erase(y);

        // perhaps remove x
        if (x != begin()) {
            y = prev(x);
            if (!mustKeep(y, x)) mustKeep(y, erase(x));
            // must re-calculate because y->p is y & x after `if` clause
        }
        else return;

        // remove lines before x
        while (y != begin()) {
            x = prev(y);
            if (x->p >= y->p) mustKeep(x, erase(y)), y = x;
            else break;
        }
    }

    ll query (ll x) {
        if (rbegin()->p != oo) {
            while (true);
        }
        return lower_bound(x)->calc(x);
    }
};

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

int rr (int l, int r, int t = 0) {
    int cur = uniform_int_distribution<int>(l, r)(rng);
    for (int i = 0; i < t; i++)
        cur = max(cur, uniform_int_distribution<int>(l, r)(rng));
    for (int i = 0; i > t; i--)
        cur = min(cur, uniform_int_distribution<int>(l, r)(rng));
    return cur;
}

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

//    lineContainer lc;
//    for (int t = 0; t < 10; t++) {
//        lc.add(rr(1, 1'000'000), rr(1, 1'000'000));
//        cout << lc.query(rr(1, 1'000'000)) << "\n";
//        cout << "hull: ";
//        for (auto it : lc) cout << "(" << it.slope << " " << it.c << " " << it.p << ") ";
//        cout << "\n";
//    }
//    cout << lc.query(10'000'000);
//
//    return 0;

    int n; cin >> n;
    vector<ll> h(n + 1), w(n + 1);

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

    lineContainer hull;
    hull.add(-2 * h[1], h[1] * h[1] - w[1]);

    for (int i = 2; i <= n; i++) {
        ll dp = hull.query(h[i]) + h[i] * h[i] + w[i - 1];
        if (i == n) return cout << dp, 0;
        hull.add(-2 * h[i], h[i] * h[i] - w[i] + dp);
    }

    return 0;
}

Compilation message (stderr)

building.cpp:32:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   32 |     ld xSect (auto x, auto y) {
      |               ^~~~
building.cpp:32:23: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   32 |     ld xSect (auto x, auto y) {
      |                       ^~~~
building.cpp:39:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   39 |     bool mustKeep (auto x, auto y) {
      |                    ^~~~
building.cpp:39:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   39 |     bool mustKeep (auto x, auto y) {
      |                            ^~~~

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