oj.uz

Submission #669151

# Submission time Handle Problem Language Result Execution time Memory
669151 2022-12-05T20:32:36 Z four_specks Building Bridges (CEOI17_building) C++17
0 / 100
 35 ms 2776 KB 
#include <bits/stdc++.h>

using namespace std;

inline namespace
{
    template <typename T>
    T fl_div(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }

    template <typename T>
    struct Line
    {
        T m, c;
        T operator()(T x) const { return m * x + c; }
    };

    template <typename T>
    struct LineContainerObject
    {
        T m, c;
        mutable T p;

        bool operator<(const LineContainerObject &i_line) const { return m < i_line.m; }
        bool operator<(T x) const { return p < x; }
    };

    template <typename T>
    struct LineContainer : multiset<LineContainerObject<T>, less<>>
    {
        void add(const Line<T> &line)
        {
            auto it1 = Base::insert({line.m, line.c, 0}), it2 = next(it1), it = it1;
            while (isect(it1, it2))
                it2 = Base::erase(it2);
            if (it != Base::begin() && isect(prev(it), it))
            {
                it--;
                isect(it, it1 = Base::erase(it1));
            }
            while (it != Base::begin() && prev(it)->p >= it->p)
            {
                it--;
                isect(it, Base::erase(next(it)));
            }
        }

        T query(T x)
        {
            auto it = Base::lower_bound(x);
            return it->m * x + it->c;
        }

    private:
        using Base = multiset<LineContainerObject<T>, less<>>;
        using Iterator = typename Base::iterator;

        inline static const T INF = numeric_limits<T>::max();

        bool isect(Iterator it, Iterator it1)
        {
            if (it1 == Base::end())
            {
                it->p = INF;
                return 0;
            }

            if (it->m == it1->m)
                it->p = it->c > it1->c ? INF : -INF;
            else
                it->p = fl_div(it1->c - it->c, it->m - it1->m);

            return it->p >= it1->p;
        }
    };

} // namespace

void solve()
{
    int n;
    cin >> n;

    vector<long> h(n), w(n);
    for (long &x : h)
        cin >> x;
    for (long &x : w)
        cin >> x;

    long add = 0;
    for (long x : w)
        add += x;

    vector<long> dp(n);
    LineContainer<long> cht;
    dp[0] = w[0];
    cht.add(Line<long>{2 * h[0], dp[0] - h[0] * h[0]});
    for (int i = 1; i < n; i++)
    {
        dp[i] = cht.query(h[i]) - h[i] * h[i] + w[i];
        cht.add(Line<long>{2 * h[i], dp[i] - h[i] * h[i]});
    }

    cout << -dp[n - 1] + add << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 2776 KB Output isn't correct
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 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -