제출 #938574

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

building

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e6 + 5;
const double eps = 1e-9;

struct Line {
    ll m, b;
    ll operator()(ll x) { return m * x + b; }
};

struct LiChao {
    int n;
    vector<Line> tree;

    LiChao(int _n) {
        n = _n + 5;
        tree.resize(4*n);
    }

    void insert(int u, int tl, int tr, Line seg) {
        if(tl + 1 == tr) {
            if(seg(tl) > tree[u](tl)) tree[u] = seg;
            return ;
        }

        int tm = (tl + tr) / 2;
        if(tree[u].m > seg.m) swap(tree[u], seg);
        if(tree[u](tm) < seg(tm)) {
            swap(tree[u], seg);
            insert(2*u+1, tl, tm, seg);
        } else insert(2*u+2, tm, tr, seg);
    }

    ll query(int u, int tl, int tr, int p) {
        if(tl + 1 == tr) return tree[u](p);
        int tm = (tl + tr) / 2;
        if(p < tm) return max(tree[u](p), query(2*u+1, tl, tm, p));
        return max(tree[u](p), query(2*u+2, tm, tr, p));
    }

    void insert(Line line) { insert(0, 0, n, line); }
    ll query(ll v) { return query(0, 0, n, v); }
};

int main() {
    int n;
    ll ans = 0;
    cin >> n;

    vector<int> h(n), w(n);
    for(int &x : h) cin >> x;
    for(int &x : w) cin >> x, ans += x;

    LiChao cht(maxn);

    vector<ll> dp(n);
    dp[0] = -w[0];
    cht.insert({ 2 * h[0], -dp[0] - h[0] * h[0] });

    for(int i=1; i<n; i++) {
        dp[i] = -cht.query(h[i]) + h[i] * h[i] - w[i];
        cht.insert({ 2 * h[i], -dp[i] - h[i] * h[i] }); 
    }

    cout << ans + dp[n-1] << '\n';
    return 0;
}

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