Submission #523620

#	Time	Username	Problem	Language	Result	Execution time	Memory
523620		KoD	Building Bridges (CEOI17_building)	C++17	100 / 100	73 ms	8216 KiB

building

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40