Submission #656393

#	Time	Username	Problem	Language	Result	Execution time	Memory
656393		AkiYuu	Building Bridges (CEOI17_building)	C++17	0 / 100	41 ms	9400 KiB

building

#include <bits/stdc++.h>
#define ll long long
#define ffw(i,a,b) for(int i = a; i<= b; i++)

using namespace std;
const int mxn= 1e5  +7;
const ll INF = 1e18;
struct line{
    ll A, B;
    ll operator()(const ll &x){
        return A*x + B;
    }
};

struct lichao{
    vector< line > tree;
    int  N;

    lichao(int _n ){
        N = _n;
        ffw(i,0,4*N + 6) tree.push_back({0,INF});
    }

    void add(line cur, ll x, int lx, int rx){
        if ( lx == rx ) {
            if ( cur(lx) < tree[x](lx) ) tree[x] = cur;
            return;
        }

        ll m = (lx + rx) / 2;
        if ( cur.A > tree[x].A  ) swap(tree[x] , cur);
        if ( cur(m) < tree[x](m) ) {
            swap(cur,tree[x]);
            add(cur, 2*x,lx,m);
        } else add(cur,2*x+1,m+1,rx);
    }

    void add(line cur){
        add(cur,1,1,N);
    }

    ll get(ll val, int x,int lx, int rx){
        if ( lx == rx) return tree[x](val);
        int m  = ( lx + rx)  /2;
        return min(tree[x](val), get(val, 2*x, lx,m) );
    }

    ll get(ll val){
        return get(val, 1,1,N);
    }
};

int n;
ll h[mxn];
ll s[mxn];
ll w[mxn];

void solve(){

    cin >> n;
    ffw(i,1,n) cin >> h[i];
    lichao bag(n + 1);

    cin >> w[1];
    s[1] = w[1];
    bag.add({2*h[1], h[1] * h[1] - s[1]});
    ffw(i,2,n){
        cin >> w[i];
        s[i] = s[i-1] + w[i];
        ll cur = bag.get(-h[i]) + h[i] * h[i] + s[i-1];
        bag.add({2*h[i], h[i] * h[i] + cur -  s[i]});
        if ( i == n )
            cout << cur << '\n';
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("xaycau.inp", "r", stdin);
//    freopen("xaycau.out", "w", stdout);

    solve();

}

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