oj.uz

Submission #608835

# Submission time Handle Problem Language Result Execution time Memory
608835 2022-07-27T10:38:18 Z OttoTheDino Building Bridges (CEOI17_building) C++17
0 / 100
 24 ms 3436 KB 
#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 inf = 1e9, 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 inf*inf;
    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, bl, mid, 2*id));
}

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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -