제출 #598751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
598751		devedude	Building Bridges (CEOI17_building)	C++17	100 / 100	52 ms	9700 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 ll inf = LLONG_MAX;

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 ll max_x;
    bool operator<(const Line &o) const {
        return a > o.a;
    }
    bool operator<(ll x) const {
        return max_x < x;
    }
};

struct LineContainer : multiset<Line, less<>> {
    ll div(ll n, ll d) { // floor division for negative and positive lls
        return n / d - ((n ^ d) < 0 && n % d);
    }
    bool isect(iterator l, iterator m) {
        // assumption: l and m are neighbouring lines, with m > l
        // do: adjust the max_x for l
        // return: l covers x after or equal to last x of m
        if (m == end()) { // handle case l is last line
            l->max_x = inf;
            return false;
        }
        if (l->a == m->a) { // prevent division by zero
            l->max_x = l->b < m->b ? inf : -inf;
        } else { // default case, intersection point of l and m floored
            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; // iterators
        //cerr << "Adding line " << cur->a << ' ' << cur->b << ' ';
        ++nex;
        while (isect(cur, nex)) nex = erase(nex); // keep erasing redundant lines after cur, note how this sets max_x of cur
        //cerr << cur->max_x << '\n';
        if (cur != begin() && isect(--pre, cur)) { // added line itself is redundant, erase and return
            cur = erase(cur);
            isect(pre, cur);
        }
        while ((cur = pre) != begin() && (--pre)->max_x >= cur->max_x) isect(pre, erase(cur)); // keep erasing redundant lines before cur, and adjust max_x of line left
    }
    ll min_y(ll x) {
        auto l = lower_bound(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]);
    }
    // for (auto &l : lc) {
    //     cerr << l.a << ' ' << l.b << ' ' << l.max_x << '\n';
    // }
    cout << dp[N-1] << '\n';
}

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