oj.uz

Submission #1024160

# Submission time Handle Problem Language Result Execution time Memory
1024160 2024-07-15T14:23:31 Z _callmelucian Building Bridges (CEOI17_building) C++14
100 / 100
 70 ms 66540 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

struct line {
    ll a, b;

    line() : a(0), b(0) {}
    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.calc(mid) < tr[k].calc(mid)) swap(tr[k], f);
        if (f.slope() > tr[k].slope())
            update(f, 2 * k, l, mid); // case 1.1
        if (f.slope() < tr[k].slope())
            update(f, 2 * k + 1, mid + 1, r); // case 1.2
    }

    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 24 ms 63060 KB Output is correct
2 Correct 25 ms 63068 KB Output is correct
3 Correct 26 ms 63088 KB Output is correct
4 Correct 26 ms 63056 KB Output is correct
5 Correct 25 ms 63068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 66368 KB Output is correct
2 Correct 65 ms 66384 KB Output is correct
3 Correct 60 ms 66456 KB Output is correct
4 Correct 58 ms 66132 KB Output is correct
5 Correct 59 ms 66264 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 63060 KB Output is correct
2 Correct 25 ms 63068 KB Output is correct
3 Correct 26 ms 63088 KB Output is correct
4 Correct 26 ms 63056 KB Output is correct
5 Correct 25 ms 63068 KB Output is correct
6 Correct 62 ms 66368 KB Output is correct
7 Correct 65 ms 66384 KB Output is correct
8 Correct 60 ms 66456 KB Output is correct
9 Correct 58 ms 66132 KB Output is correct
10 Correct 59 ms 66264 KB Output is correct
11 Correct 68 ms 66396 KB Output is correct
12 Correct 70 ms 66388 KB Output is correct
13 Correct 66 ms 66480 KB Output is correct
14 Correct 68 ms 66540 KB Output is correct
15 Correct 59 ms 66132 KB Output is correct
16 Correct 60 ms 66132 KB Output is correct
17 Correct 42 ms 66384 KB Output is correct
18 Correct 37 ms 66388 KB Output is correct