Submission #939006

#	Time	Username	Problem	Language	Result	Execution time	Memory
939006		vjudge1	Building Bridges (CEOI17_building)	C++17	100 / 100	45 ms	9052 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const int inf = 1e18;

const int C = 2e6;

struct Lichao{
    struct Line{
        int m, c;

        Line(int m = 0, int c = inf) : m(m), c(c) {}

        int operator ()(int x){ return m * x + c; }
    };
    struct Info{
        Line sg;

        Info *lf, *rg;

        Info(Line sg) : sg(sg), lf(0), rg(0) {}
    };
    Info *root = new Info({0, inf});
    void ins(Info *v, int l, int r, Line nw){
        if ( l == r ){
            if ( v->sg(l) > nw(l) ){
                v->sg = nw;
            } return;
        }
        int md = (l + r) >> 1;
        if ( v->sg.m > nw.m ) swap(v->sg, nw);
        if ( v->sg(md) <= nw(md) ){
            if ( v->lf ){
                ins(v->lf, l, md, nw);
            } else v->lf = new Info(nw);
        } else{
            swap(v->sg, nw);
            if ( v->rg ){
                ins(v->rg, md + 1, r, nw);
            } else v->rg = new Info(nw);
        }
    }
    void ins(Line nw){
        ins(root, -C, C, nw);
    }

    int get(Info *v, int l, int r, int x){
        if ( l == r ){
            return v->sg(x);
        }
        int md = (l + r) >> 1, ret = v->sg(x);
        if ( x <= md ){
            if ( v->lf ){
                chmin(ret, get(v->lf, l, md, x));
            }
        } else{
            if ( v->rg ){
                chmin(ret, get(v->rg, md + 1, r, x));
            }
        } return ret;
    }
    int get(int x){
        return get(root, -C, C, x);
    }

    void clear(){ root = new Info ({0, inf}); }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <int> h(n), w(n);
    for ( auto &u: h ) cin >> u;
    for ( auto &u: w ) cin >> u;
    vector <int> pf(n);
    for ( int i = 0; i < n; i++ ){
        pf[i] = (i ? pf[i - 1] : 0) + w[i];
    }
    Lichao lch;
    vector <int> dp(n);
    auto ins = [&](int j){
        lch.ins({-2 * h[j],  h[j] * h[j] - pf[j] + dp[j]});
    };
    ins(0);
    for ( int i = 1; i < n; i++ ){
        dp[i] = lch.get(h[i]) + h[i] * h[i] + pf[i - 1];
        ins(i);
    }
    cout << dp.back();

    cout << '\n';
}

/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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