oj.uz

Submission #1023142

# Submission time Handle Problem Language Result Execution time Memory
1023142 2024-07-14T11:00:18 Z _callmelucian Building Bridges (CEOI17_building) C++14
100 / 100
 69 ms 66508 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 a, b;

    line() : a(0), b() {}
    line (ll a, ll b) : a(a), b(b) {}

    ll calc (ll x) { return a * x + b; }

    ll slope() { return a; }
};

struct liChao {
    vector<line> tr;

    liChao() {}
    liChao (int sz) : tr(4 * sz, line(0, LLONG_MAX)) {}

    void update (line f, int k, int l, int r) {
        if (l == r) {
            tr[k] = (f.calc(l) < tr[k].calc(l) ? f : tr[k]);
            return;
        }
        int mid = (l + r) >> 1;
        if (f.slope() < tr[k].slope()) swap(tr[k], f);
        if (tr[k].calc(mid) < f.calc(mid)) { // case 1.1 and 2.1
            update(f, 2 * k, l, mid);
        }
        else { // case 1.2 and 2.2
            update(tr[k], 2 * k + 1, mid + 1, r);
            tr[k] = f;
        }
    }

    ll query (int pos, int k, int l, int r) {
        ll cur = tr[k].calc(pos);
        int mid = (l + r) >> 1;
        if (l == r) return cur;
        if (l <= pos && pos <= mid)
            return min(cur, query(pos, 2 * k, l, mid));
        else return min(cur, query(pos, 2 * k + 1, mid + 1, 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(line(f1(1), f2(1)), 1, 0, M);

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

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63068 KB Output is correct
2 Correct 26 ms 63064 KB Output is correct
3 Correct 25 ms 63060 KB Output is correct
4 Correct 35 ms 63068 KB Output is correct
5 Correct 29 ms 62924 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 66444 KB Output is correct
2 Correct 61 ms 66384 KB Output is correct
3 Correct 59 ms 66384 KB Output is correct
4 Correct 61 ms 66344 KB Output is correct
5 Correct 58 ms 66132 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 63068 KB Output is correct
2 Correct 26 ms 63064 KB Output is correct
3 Correct 25 ms 63060 KB Output is correct
4 Correct 35 ms 63068 KB Output is correct
5 Correct 29 ms 62924 KB Output is correct
6 Correct 68 ms 66444 KB Output is correct
7 Correct 61 ms 66384 KB Output is correct
8 Correct 59 ms 66384 KB Output is correct
9 Correct 61 ms 66344 KB Output is correct
10 Correct 58 ms 66132 KB Output is correct
11 Correct 69 ms 66508 KB Output is correct
12 Correct 67 ms 66388 KB Output is correct
13 Correct 57 ms 66384 KB Output is correct
14 Correct 69 ms 66384 KB Output is correct
15 Correct 58 ms 66128 KB Output is correct
16 Correct 57 ms 66128 KB Output is correct
17 Correct 49 ms 66384 KB Output is correct
18 Correct 48 ms 66388 KB Output is correct