oj.uz

Submission #606934

# Submission time Handle Problem Language Result Execution time Memory
606934 2022-07-26T10:09:19 Z pakhomovee Building Bridges (CEOI17_building) C++17
100 / 100
 81 ms 67400 KB 
#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define int long long
const int inf = 1e18;
const int maxn = 1e6 + 1;

struct line {
    int k, b;
    line() {}
    line(int k, int b): k(k), b(b) {}
    int get(int x) { return k * x + b; }
};

line tree[maxn * 4];

void init(line l) {
    fill(tree, tree + maxn * 4, l);
}

int get(int i, int l, int r, int x) {
    if (l + 1 == r) return tree[i].get(x);
    int m = (l + r) / 2;
    if (x < m) return min(tree[i].get(x), get(i * 2, l, m, x));
    return min(tree[i].get(x), get(i * 2 + 1, m, r, x));
}

void upd(int i, int l, int r, line ln) {
    int m = (l + r) / 2;
    bool lt = ln.get(l) < tree[i].get(l);
    bool md = ln.get(m) < tree[i].get(m);
    if (md) {
        swap(tree[i], ln);
    }
    if (l + 1 == r) return;
    if (lt != md) {
        upd(i * 2, l, m, ln);
    } else {
        upd(i * 2 + 1, m, r, ln);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> h(n);
    for (int& i : h) cin >> i;
    vector<int> w(n);
    for (int& i : w) cin >> i;
    vector<int> dp(n, inf);
    dp[0] = 0;
    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + w[i - 1];
    init(line(-2 * h[0], h[0] * h[0] - w[0]));
    for (int i = 1; i < n; ++i) {
        dp[i] = get(1, 0, maxn, h[i]) + h[i] * h[i] + pref[i];
        upd(1, 0, maxn, line(-2 * h[i], dp[i] - pref[i + 1] + h[i] * h[i]));
    }
    cout << dp.back();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62796 KB Output is correct
2 Correct 34 ms 62800 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 28 ms 62964 KB Output is correct
5 Correct 27 ms 62868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 65996 KB Output is correct
2 Correct 65 ms 67104 KB Output is correct
3 Correct 65 ms 67048 KB Output is correct
4 Correct 66 ms 67012 KB Output is correct
5 Correct 80 ms 66900 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62796 KB Output is correct
2 Correct 34 ms 62800 KB Output is correct
3 Correct 26 ms 62932 KB Output is correct
4 Correct 28 ms 62964 KB Output is correct
5 Correct 27 ms 62868 KB Output is correct
6 Correct 63 ms 65996 KB Output is correct
7 Correct 65 ms 67104 KB Output is correct
8 Correct 65 ms 67048 KB Output is correct
9 Correct 66 ms 67012 KB Output is correct
10 Correct 80 ms 66900 KB Output is correct
11 Correct 78 ms 67400 KB Output is correct
12 Correct 69 ms 67092 KB Output is correct
13 Correct 81 ms 67152 KB Output is correct
14 Correct 80 ms 67252 KB Output is correct
15 Correct 69 ms 66876 KB Output is correct
16 Correct 62 ms 66976 KB Output is correct
17 Correct 55 ms 67148 KB Output is correct
18 Correct 58 ms 67044 KB Output is correct