Submission #669579

#	Time	Username	Problem	Language	Result	Execution time	Memory
669579		four_specks	Building Bridges (CEOI17_building)	C++17	100 / 100	54 ms	8908 KiB

building

#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 it = this->insert({line.m, line.c, 0});
            while (isect(it))
                this->erase(next(it));
            if (it != this->begin() && isect(--it))
            {
                this->erase(next(it));
                isect(it);
            }
            while (it != this->begin() && isect(--it))
            {
                this->erase(next(it));
                isect(it);
            }
        }

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

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

        bool isect(typename multiset<LineContainerObject<T>, less<>>::iterator it)
        {
            if (next(it) == this->end())
            {
                it->p = INF;
                return 0;
            }

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

            return it->p >= next(it)->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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40