oj.uz

Submission #569840

# Submission time Handle Problem Language Result Execution time Memory
569840 2022-05-27T21:39:16 Z four_specks Building Bridges (CEOI17_building) C++17
100 / 100
 57 ms 9772 KB 
#include <bits/stdc++.h>

using namespace std;

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

    struct LineContainer : multiset<Line, less<>>
    {
        // (for doubles, use inf = 1/.0, div(a,b) = a/b)
        static const long inf = LONG_MAX;
        long div(long a, long 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(long k, long 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));
        }
        long query(long x)
        {
            assert(!empty());
            auto l = *lower_bound(x);
            return l.k * x + l.m;
        }
    };

} // 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 cht;
    dp[0] = w[0];
    cht.add(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(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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 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 40 ms 3732 KB Output is correct
2 Correct 41 ms 3744 KB Output is correct
3 Correct 37 ms 3668 KB Output is correct
4 Correct 34 ms 3540 KB Output is correct
5 Correct 37 ms 4704 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 40 ms 3732 KB Output is correct
7 Correct 41 ms 3744 KB Output is correct
8 Correct 37 ms 3668 KB Output is correct
9 Correct 34 ms 3540 KB Output is correct
10 Correct 37 ms 4704 KB Output is correct
11 Correct 40 ms 3792 KB Output is correct
12 Correct 38 ms 3668 KB Output is correct
13 Correct 33 ms 3788 KB Output is correct
14 Correct 40 ms 3828 KB Output is correct
15 Correct 57 ms 9772 KB Output is correct
16 Correct 47 ms 4704 KB Output is correct
17 Correct 28 ms 3676 KB Output is correct
18 Correct 21 ms 3772 KB Output is correct