Submission #598152

#	Time	Username	Problem	Language	Result	Execution time	Memory
598152		devedude	Building Bridges (CEOI17_building)	C++17	0 / 100	33 ms	2596 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef tuple<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)

const double inf = 1/.0;

void run();

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    run();
}

inline ll sqr(ll x) {
    return x * x;
}

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

struct LineContainer : multiset<Line, less<>> {
    ll div(ll n, ll d) {
        return (double)n / d;// - ((n ^ d) < 0 && n % d);
    }
    bool isect(iterator l, iterator m) {
        if (m == end()) {
            l->max_x = inf;
            return false;
        }
        if (l->a == m->a) {
            l->max_x = l->b < m->b ? inf : -inf;
        } else {
            l->max_x = div(m->b - l->b, l->a - m->a);
        }
        return l->max_x >= m->max_x;
    }
    void add(ll a, ll b) {
        auto cur = insert({a, b, 0}), pre = cur, nex = cur;
        ++nex;
        while (isect(cur, nex)) nex = erase(nex);
        if (cur != begin() && isect(--pre, cur)) {
            cur = erase(cur);
        }
        while ((cur = pre) != begin() && (--pre)->max_x >= cur->max_x) {
            isect(pre, erase(cur));
        }
    }
    ll min_y(ll x) {
        auto l = lower_bound((double)x);
        //cerr << "Minimal for x = " << x << " is line a = " << l->a << " b = " << l->b << " at y = " << l->y(x) << '\n';
        return l->a * x + l->b;
    }
};

int N;
ll h[100005];
ll W[100005];
ll dp[100005];

void run() {
    cin >> N;
    FOR(i, 0, N) cin >> h[i];
    FOR(i, 0, N) {
        ll w; cin >> w;
        W[i+1] = W[i] + w;
    }
    LineContainer lc;
    FOR(i, 1, N) {
        lc.add(-2*h[i-1], dp[i-1] + h[i-1]*h[i-1] - W[i]);
        dp[i] = h[i]*h[i] + W[i] + lc.min_y(h[i]);
    }
    cout << dp[N-1] << '\n';
}

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