oj.uz

Submission #704206

# Submission time Handle Problem Language Result Execution time Memory
704206 2023-03-01T23:04:39 Z finn__ Building Bridges (CEOI17_building) C++17
30 / 100
 3000 ms 2600 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

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 = 0, right = 0, f = LinearFn<T>(0, numeric_limits<T>::max()); }

    void insert(LinearFn<T> g, T l, T r)
    {
        T mid = (l + r) / 2;
        if (g(mid) < f(mid))
            swap(g, f);
        if (r - l == 1)
            return;
        if ((g(l) < f(l)) ^ (g(mid) < f(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)
            y = min(y, left->get_min(x, l, (l + r) / 2));
        if (right)
            y = min(y, right->get_min(x, (l + r) / 2, r));
        return y;
    }
};

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

int64_t h[N], w[N];

int main()
{
    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';
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3060 ms 2600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Execution timed out 3060 ms 2600 KB Time limit exceeded
7 Halted 0 ms 0 KB -