Submission #939394

#	Time	Username	Problem	Language	Result	Execution time	Memory
939394		caterpillow	Building Bridges (CEOI17_building)	C++17	60 / 100	39 ms	9812 KiB

building

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1;i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;

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

ll sign = -1; // -1 for min, 1 for max
struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    ll div(ll a, ll b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b); 
    }
    bool isect(auto x, auto y) {
        if (y == end()) { x->p = INF; return false; }
        if (x->a == y->a) x->p = x->b > y->b ? INF : -INF;
        else x->p = div(y->b - x->b, x->a - y->a);
        return x->p >= y->p;
    }
    void add(ll a, ll b) {
    a *= sign, b *= sign;
        auto z = insert({a, b, 0}), y = z++, x = y;
        while (isect(y, z)) z = erase(z);
        if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p) isect(x, erase(y));
    }
    ll query(ll x) {
        assert(size());
        auto l = *lower_bound(x);
        return -l.a * x - l.b;
    }
};

/*

assume all bridges are getting broken already and add back the ones that are not

dp[i] = min(h[i] - h[j]) ^ 2 + d[j]) - w[i]
dp[i] = h[i] ^ 2 - w[i] + min(-2 * h[i] * h[j] + h[j]^2 + dp[j])

*/

ll n;
vt<ll> h, w;

main() {    
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n;
    h = w = vt<ll>(n);
    F0R (i, n) cin >> h[i];
    F0R (i, n) cin >> w[i];

    vt<ll> dp(n);
    dp[0] = -w[0];

    LineContainer lc;
    lc.add(-2 * h[0], h[0] * h[0] + dp[0]);

    FOR (i, 1, n) {
        dp[i] = h[i] * h[i] - w[i] + lc.query(h[i]);
        lc.add(-2 * h[i], h[i] * h[i] + dp[i]);
    }

    cout << dp[n - 1] + accumulate(all(w), 0) << endl;
}

Compilation message (stderr)

building.cpp:31:16: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   31 |     bool isect(auto x, auto y) {
      |                ^~~~
building.cpp:31:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   31 |     bool isect(auto x, auto y) {
      |                        ^~~~
building.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main() {
      | ^~~~

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