oj.uz

Submission #677147

# Submission time Handle Problem Language Result Execution time Memory
677147 2023-01-02T12:17:54 Z leeh18 Building Bridges (CEOI17_building) C++17
100 / 100
 46 ms 8920 KB 
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

struct Line {
    mutable i64 k, m, p;
    bool operator<(const Line &o) const { return k < o.k; }
    bool operator<(i64 x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
    // (for doubles, use inf = 1/.0, div(a,b) = a/b)
    static const i64 inf = LLONG_MAX;
    i64 div(i64 a, i64 b) { // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool isect(iterator x, iterator y) {
        if (y == end())
            return x->p = inf, 0;
        if (x->k == y->k)
            x->p = x->m > y->m ? inf : -inf;
        else
            x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    void add(i64 k, i64 m) {
        auto z = insert({k, m, 0}), y = z++, x = y;
        while (isect(y, z))
            z = erase(z);
        if (x != begin() && isect(--x, y))
            isect(x, y = erase(y));
        while ((y = x) != begin() && (--x)->p >= y->p)
            isect(x, erase(y));
    }
    i64 query(i64 x) {
        assert(!empty());
        auto l = *lower_bound(x);
        return l.k * x + l.m;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N;
    cin >> N;
    vector<i64> h(N), W(N);
    copy_n(istream_iterator<i64>(cin), N, begin(h));
    copy_n(istream_iterator<i64>(cin), N, begin(W));
    partial_sum(begin(W), end(W), begin(W));
    LineContainer cht;
    cht.add(2 * h[0], W[0] - h[0] * h[0]);
    auto dp = 0LL;
    for (auto i = 1; i < N; ++i) {
        dp = h[i] * h[i] + W[i - 1] - cht.query(h[i]);
        cht.add(2 * h[i], W[i] - h[i] * h[i] - dp);
    }
    cout << dp;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 356 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2980 KB Output is correct
2 Correct 38 ms 2912 KB Output is correct
3 Correct 39 ms 3036 KB Output is correct
4 Correct 34 ms 2788 KB Output is correct
5 Correct 33 ms 4012 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 316 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 356 KB Output is correct
6 Correct 36 ms 2980 KB Output is correct
7 Correct 38 ms 2912 KB Output is correct
8 Correct 39 ms 3036 KB Output is correct
9 Correct 34 ms 2788 KB Output is correct
10 Correct 33 ms 4012 KB Output is correct
11 Correct 34 ms 3116 KB Output is correct
12 Correct 36 ms 2940 KB Output is correct
13 Correct 27 ms 2900 KB Output is correct
14 Correct 38 ms 3032 KB Output is correct
15 Correct 46 ms 8920 KB Output is correct
16 Correct 33 ms 4004 KB Output is correct
17 Correct 19 ms 2912 KB Output is correct
18 Correct 23 ms 2892 KB Output is correct