Submission #608900

#	Time	Username	Problem	Language	Result	Execution time	Memory
608900		OttoTheDino	Building Bridges (CEOI17_building)	C++17	100 / 100	51 ms	5612 KiB

building

#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
typedef long long ll;

const ll mx = 1e6;

ll seg[4*mx+1], h[mx+1], w[mx+1], dp[mx+1];

void upd (ll u, ll bl, ll br, ll id) {
    if (!seg[id]) {
        seg[id] = u;
        return;
    }
    ll mid = (bl+br)/2;
    if (dp[u]-2*h[u]*mid<dp[seg[id]]-2*h[seg[id]]*mid) swap (seg[id], u);
    if (bl==br) return;
    if (-2*h[u]<-2*h[seg[id]]) upd (u, mid+1, br, 2*id+1);
    else if (-2*h[u]>-2*h[seg[id]]) upd (u, bl, mid, 2*id);
}

ll qry (ll x, ll bl, ll br, ll id) {
    if (!seg[id]) return 1e18;
    if (bl==br) return dp[seg[id]] - 2*h[seg[id]]*x;
    ll mid = (bl+br)/2;
    if (x<=mid) return min(dp[seg[id]]-2*h[seg[id]]*x, qry(x, bl, mid, 2*id));
    return min(dp[seg[id]]-2*h[seg[id]]*x, qry(x, mid+1, br, 2*id+1));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ll n, s = 0;
    cin >> n;

    rep (i,1,n) cin >> h[i];
    rep (i,1,n) {
        cin >> w[i];
        s += w[i];
    }

    dp[1] = h[1]*h[1]-w[1];

    upd (1, 0, mx, 1); 

    rep (i,2,n) {
        dp[i] = qry (h[i], 0, mx, 1) + h[i]*h[i]-w[i];

        if (i==n) cout << s+dp[n] << "\n";

        else {
            dp[i] += h[i]*h[i];
            upd (i, 1, mx, 1); 
        }
    }

    return 0;
}

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