oj.uz

Submission #534666

# Submission time Handle Problem Language Result Execution time Memory
534666 2022-03-08T13:26:15 Z alextodoran Building Bridges (CEOI17_building) C++17
100 / 100
 92 ms 68680 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;
const int H_MAX = 2000000;

const ll INF = LLONG_MAX;

int n;
int h[N_MAX + 2];
int w[N_MAX + 2];

ll dp[N_MAX + 2];

struct Line {
    int a; ll b;
    ll operator () (const int &x) const {
        return (ll) a * x + b;
    }
};

Line LiChao[H_MAX * 4 + 2];

void build (int node, int l, int r) {
    LiChao[node] = Line{0, -INF};
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);
}
void build () {
    build(1, 1, H_MAX);
}
void update (int node, int l, int r, Line ln) {
    if (l == r) {
        if (LiChao[node](l) < ln(l)) {
            swap(LiChao[node], ln);
        }
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (LiChao[node].a > ln.a) {
        swap(LiChao[node], ln);
    }
    if (LiChao[node](mid) < ln(mid)) {
        swap(LiChao[node], ln);
        update(lSon, l, mid, ln);
    } else {
        update(rSon, mid + 1, r, ln);
    }
}
void update (Line ln) {
    update(1, 1, H_MAX, ln);
}
ll query (int node, int l, int r, int x) {
    if (l == r) {
        return LiChao[node](x);
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (x <= mid) {
        return max(LiChao[node](x), query(lSon, l, mid, x));
    } else {
        return max(LiChao[node](x), query(rSon, mid + 1, r, x));
    }
}
ll query (int x) {
    return query(1, 1, H_MAX, x);
}

void insertDp (int i) {
    update(Line{2 * h[i], -dp[i] - (ll) h[i] * h[i]});
}
ll getMin (int i) {
    return w[i] + (ll) h[i] * h[i] - query(h[i]);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

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

    ll sumw = 0;
    for (int i = 1; i <= n; i++) {
        sumw += w[i];
        w[i] = -w[i];
    }

    build();
    dp[1] = w[1]; insertDp(1);
    for (int i = 2; i <= n; i++) {
        dp[i] = getMin(i); insertDp(i);
    }
    cout << dp[n] + sumw << "\n";

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65940 KB Output is correct
2 Correct 36 ms 65860 KB Output is correct
3 Correct 35 ms 65976 KB Output is correct
4 Correct 35 ms 65904 KB Output is correct
5 Correct 37 ms 65984 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 68680 KB Output is correct
2 Correct 80 ms 68548 KB Output is correct
3 Correct 74 ms 68528 KB Output is correct
4 Correct 84 ms 68400 KB Output is correct
5 Correct 73 ms 68420 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 65940 KB Output is correct
2 Correct 36 ms 65860 KB Output is correct
3 Correct 35 ms 65976 KB Output is correct
4 Correct 35 ms 65904 KB Output is correct
5 Correct 37 ms 65984 KB Output is correct
6 Correct 92 ms 68680 KB Output is correct
7 Correct 80 ms 68548 KB Output is correct
8 Correct 74 ms 68528 KB Output is correct
9 Correct 84 ms 68400 KB Output is correct
10 Correct 73 ms 68420 KB Output is correct
11 Correct 86 ms 68616 KB Output is correct
12 Correct 82 ms 68420 KB Output is correct
13 Correct 92 ms 68616 KB Output is correct
14 Correct 92 ms 68624 KB Output is correct
15 Correct 68 ms 68404 KB Output is correct
16 Correct 78 ms 68448 KB Output is correct
17 Correct 63 ms 68660 KB Output is correct
18 Correct 67 ms 68556 KB Output is correct