oj.uz

Submission #882008

# Submission time Handle Problem Language Result Execution time Memory
882008 2023-12-02T12:02:07 Z _callmelucian Building Bridges (CEOI17_building) C++14
100 / 100
 62 ms 71260 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(v) v.begin(), v.end()

struct line {
    ll slope, c;
    line (ll u = 0, ll v = 0) : slope(u), c(v) {}
    ll calc (ll x) {return slope * x + c;}
};

struct liChao {
    vector<line> tr;
    liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)) {}

    void update (int k, line seg, int l, int r) {
        if (l + 1 == r) {
            if (seg.calc(l) < tr[k].calc(l)) tr[k] = seg;
            return;
        }
        int mid = (l + r) / 2;
        if (seg.slope > tr[k].slope) swap(seg, tr[k]); // seg must have lower slope
        if (seg.calc(mid) < tr[k].calc(mid)) {
            update(2 * k, tr[k], l, mid);
            tr[k] = seg;
        }
        else update(2 * k + 1, seg, mid, r);
    }

    ll query (int pos, int k, int l, int r) {
        if (l + 1 == r) return tr[k].calc(pos);
        int mid = (l + r) / 2;
        if (pos < mid) return min(tr[k].calc(pos), query(pos, 2 * k, l, mid));
        return min(tr[k].calc(pos), query(pos, 2 * k + 1, mid, r));
    }
};

const int M = 1e6 + 1;
ll dp[M], h[M], w[M];

ll f1 (int k) {
    return -2 * h[k];
}

ll f2 (int k) {
    return dp[k] + h[k] * h[k] - w[k];
}

ll f3 (int k) {
    return h[k] * h[k] + w[k - 1];
}

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

    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i] += w[i - 1];
    }

    liChao tree(M);
    tree.update(1, line(f1(1), f2(1)), 0, M);

    for (int i = 2; i <= n; i++) {
        dp[i] = tree.query(h[i], 1, 0, M) + f3(i);
        tree.update(1, line(f1(i), f2(i)), 0, M);
    }
    cout << dp[n];

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65112 KB Output is correct
2 Correct 10 ms 65116 KB Output is correct
3 Correct 12 ms 65116 KB Output is correct
4 Correct 12 ms 65116 KB Output is correct
5 Correct 11 ms 65116 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 70996 KB Output is correct
2 Correct 45 ms 70992 KB Output is correct
3 Correct 46 ms 71128 KB Output is correct
4 Correct 41 ms 70988 KB Output is correct
5 Correct 37 ms 70996 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 65112 KB Output is correct
2 Correct 10 ms 65116 KB Output is correct
3 Correct 12 ms 65116 KB Output is correct
4 Correct 12 ms 65116 KB Output is correct
5 Correct 11 ms 65116 KB Output is correct
6 Correct 49 ms 70996 KB Output is correct
7 Correct 45 ms 70992 KB Output is correct
8 Correct 46 ms 71128 KB Output is correct
9 Correct 41 ms 70988 KB Output is correct
10 Correct 37 ms 70996 KB Output is correct
11 Correct 52 ms 71260 KB Output is correct
12 Correct 56 ms 70992 KB Output is correct
13 Correct 43 ms 71248 KB Output is correct
14 Correct 62 ms 71212 KB Output is correct
15 Correct 37 ms 70944 KB Output is correct
16 Correct 37 ms 71000 KB Output is correct
17 Correct 29 ms 71252 KB Output is correct
18 Correct 30 ms 71028 KB Output is correct