제출 #258026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
258026		dolphingarlic	Building Bridges (CEOI17_building)	C++14	0 / 100	49 ms	4600 KiB

building

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Line {
    ll m, c;
    inline ll operator()(ll x) { return m * x + c; }
} segtree[4000001];

void insert(Line seg, int node = 1, int l = 0, int r = 1000000) {
    if (l == r) {
        if (seg(l) < segtree[node](l)) segtree[node] = seg;
    } else {
        int mid = (l + r) / 2;
        if (segtree[node].m <= seg.m) swap(segtree[node], seg);
        if (segtree[node](mid) > seg(mid)) {
            swap(segtree[node], seg);
            insert(seg, node * 2, l, mid);
        } else insert(seg, node * 2 + 1, mid + 1, r);
    }
}

ll query(ll x, int node = 1, int l = 0, int r = 1000000) {
    if (l == r) return segtree[node](x);
    int mid = (l + r) / 2;
    if (x < mid) return min(segtree[node](x), query(x, node * 2, l, mid));
    return min(segtree[node](x), query(x, node * 2 + 1, mid + 1, r));
}

ll h[100001], w[100001], tot = 0, dp[100001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    FOR(i, 1, n + 1) cin >> h[i];
    FOR(i, 1, n + 1) {
        cin >> w[i];
        tot += w[i];
    }

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

    cout << tot + dp[n];
    return 0;
}

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