oj.uz

Submission #704212

# Submission time Handle Problem Language Result Execution time Memory
704212 2023-03-01T23:23:02 Z finn__ Building Bridges (CEOI17_building) C++17
100 / 100
 43 ms 11544 KB 
#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct LinearFn
{
    T m, t;

    LinearFn() {}

    LinearFn(T m_, T t_) { m = m_, t = t_; }

    T operator()(T x) const { return m * x + t; }
};

template <typename T>
struct LiChaoNode
{
    LiChaoNode<T> *left, *right;
    LinearFn<T> f;

    LiChaoNode()
    {
        left = right = 0;
        // If function values go higher, change the default maximum.
        f = LinearFn<T>(0, numeric_limits<T>::max() / 4);
    }

    void insert(LinearFn<T> g, T l, T r)
    {
        T mid = (l + r) / 2;
        if (g(mid) < f(mid))
            swap(f, g);
        if (r - l == 1)
            return;
        if ((f(l) < g(l)) ^ (f(mid) < g(mid)))
        {
            if (!left)
                left = new LiChaoNode();
            left->insert(g, l, (l + r) / 2);
        }
        else
        {
            if (!right)
                right = new LiChaoNode();
            right->insert(g, (l + r) / 2, r);
        }
    }

    T get_min(T x, T l, T r)
    {
        T y = f(x);
        if (left && x < (l + r) / 2)
            y = min(y, left->get_min(x, l, (l + r) / 2));
        if (right && x >= (l + r) / 2)
            y = min(y, right->get_min(x, (l + r) / 2, r));
        return y;
    }

    void destroy()
    {
        if (left)
            left->destroy();
        if (right)
            right->destroy();
        delete left;
        delete right;
    }
};

#define N 100000
#define H (1 << 21)

int64_t h[N], w[N];

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

    size_t n;
    cin >> n;

    int64_t wsum = 0;
    for (size_t i = 0; i < n; i++)
        cin >> h[i];
    for (size_t i = 0; i < n; i++)
        cin >> w[i], wsum += w[i];

    LiChaoNode<int64_t> root;
    root.insert(LinearFn<int64_t>(-2 * h[0], h[0] * h[0] - w[0]), 0, H);

    for (size_t i = 1; i < n; i++)
    {
        int64_t y = root.get_min(h[i], 0, H);
        LinearFn<int64_t> g(-2 * h[i], y + 2 * h[i] * h[i] - w[i]);
        root.insert(g, 0, H);

        if (i == n - 1)
            cout << wsum + g.t - h[i] * h[i] << '\n';
    }

    root.destroy();
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2436 KB Output is correct
2 Correct 40 ms 3536 KB Output is correct
3 Correct 40 ms 3532 KB Output is correct
4 Correct 36 ms 2900 KB Output is correct
5 Correct 35 ms 7768 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 39 ms 2436 KB Output is correct
7 Correct 40 ms 3536 KB Output is correct
8 Correct 40 ms 3532 KB Output is correct
9 Correct 36 ms 2900 KB Output is correct
10 Correct 35 ms 7768 KB Output is correct
11 Correct 41 ms 4296 KB Output is correct
12 Correct 43 ms 4860 KB Output is correct
13 Correct 32 ms 3104 KB Output is correct
14 Correct 43 ms 4840 KB Output is correct
15 Correct 41 ms 11544 KB Output is correct
16 Correct 35 ms 7736 KB Output is correct
17 Correct 22 ms 2944 KB Output is correct
18 Correct 21 ms 2908 KB Output is correct