oj.uz

Submission #523620

# Submission time Handle Problem Language Result Execution time Memory
523620 2022-02-08T01:22:10 Z KoD Building Bridges (CEOI17_building) C++17
100 / 100
 73 ms 8216 KB 
#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using i64 = std::int64_t;

constexpr i64 INF = std::numeric_limits<i64>::max() / 2;

struct Line {
    i64 a, b;
    explicit Line(const i64 a = 0, const i64 b = INF) : a(a), b(b) {}
    i64 eval(const i64 x) const { return a * x + b; }
};

struct LiChaoTree {
    int logn, size;
    vector<i64> coord;
    vector<Line> line;
    explicit LiChaoTree(const vector<i64>& vec) {
        logn = 0;
        while ((1 << logn) < (int)vec.size()) {
            logn += 1;
        }
        size = 1 << logn;
        coord = vec;
        std::sort(coord.begin(), coord.end());
        coord.resize(size, coord.back());
        line.resize(2 * size, Line());
    }
    void add(const Line& l) {
        add_rec(1, 0, size - 1, l);
    }
    void add_rec(const int k, const int l, const int r, Line add) {
        const int m = (l + r) / 2;
        if (add.eval(coord[m]) < line[k].eval(coord[m])) {
            std::swap(add, line[k]);
        }
        if (add.eval(coord[l]) < line[k].eval(coord[l])) {
            add_rec(2 * k, l, m, add);
        }
        if (add.eval(coord[r]) < line[k].eval(coord[r])) {
            add_rec(2 * k + 1, m + 1, r, add);
        }
    }
    i64 eval(const i64 x) const {
        int k = std::lower_bound(coord.begin(), coord.end(), x) - coord.begin() + size;
        i64 ret = INF;
        while (k > 0) {
            ret = std::min(ret, line[k].eval(x));
            k >>= 1;
        }
        return ret;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    vector<i64> H(N), W(N);
    for (auto& x : H) {
        std::cin >> x;
    }
    for (auto& x : W) {
        std::cin >> x;
    }
    for (int i = 0; i < N - 1; ++i) {
        W[i + 1] += W[i];
    }
    LiChaoTree lct(H);
    i64 last = 0;
    for (int i = 1; i < N; ++i) {
        lct.add(Line(-2 * H[i - 1], H[i - 1] * H[i - 1] - W[i - 1] + last));
        last = lct.eval(H[i]) + H[i] * H[i] + W[i - 1];
    }
    std::cout << last << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 1 ms 316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 8020 KB Output is correct
2 Correct 55 ms 7988 KB Output is correct
3 Correct 56 ms 7984 KB Output is correct
4 Correct 63 ms 7988 KB Output is correct
5 Correct 38 ms 7916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 55 ms 8020 KB Output is correct
7 Correct 55 ms 7988 KB Output is correct
8 Correct 56 ms 7984 KB Output is correct
9 Correct 63 ms 7988 KB Output is correct
10 Correct 38 ms 7916 KB Output is correct
11 Correct 58 ms 8216 KB Output is correct
12 Correct 73 ms 8012 KB Output is correct
13 Correct 58 ms 8116 KB Output is correct
14 Correct 57 ms 8176 KB Output is correct
15 Correct 37 ms 7860 KB Output is correct
16 Correct 51 ms 7868 KB Output is correct
17 Correct 21 ms 7988 KB Output is correct
18 Correct 22 ms 7984 KB Output is correct