oj.uz

Submission #835806

# Submission time Handle Problem Language Result Execution time Memory
835806 2023-08-23T20:32:02 Z elkernos Building Bridges (CEOI17_building) C++17
100 / 100
 62 ms 8972 KB 
// clang-format off
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
// template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; }
sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
struct { template <class T> operator T() { T x; cin >> x; return x; } } in;
#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using i64 = long long;
// #define int long long
// clang-format on

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

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

int32_t main()
{
    int n = in;
    vector<int> h(n + 1), w(n + 1);
    for(int i = 1; i <= n; i++) h[i] = in;
    for(int i = 1; i <= n; i++) w[i] = in;
    vector<i64> dp(n + 1);
    dp[1] = -w[1];
    auto sq = [](int a) { return (i64)a * a; };
    kactl::LineContainer cht;
    cht.add(-2 * h[1], dp[1] + sq(h[1]));
    for(int i = 2; i <= n; i++) {
        dp[i] = cht.query(h[i]) - w[i] + sq(h[i]);
        cht.add(-2 * h[i], dp[i] + sq(h[i]));
    }
    i64 sum = accumulate(w.begin() + 1, w.end(), 0ll);
    cout << sum + dp[n] << endl;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1868 KB Output is correct
2 Correct 54 ms 2960 KB Output is correct
3 Correct 54 ms 2848 KB Output is correct
4 Correct 51 ms 2764 KB Output is correct
5 Correct 48 ms 3916 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 54 ms 1868 KB Output is correct
7 Correct 54 ms 2960 KB Output is correct
8 Correct 54 ms 2848 KB Output is correct
9 Correct 51 ms 2764 KB Output is correct
10 Correct 48 ms 3916 KB Output is correct
11 Correct 56 ms 3080 KB Output is correct
12 Correct 56 ms 2928 KB Output is correct
13 Correct 51 ms 2964 KB Output is correct
14 Correct 57 ms 3088 KB Output is correct
15 Correct 62 ms 8972 KB Output is correct
16 Correct 53 ms 4056 KB Output is correct
17 Correct 43 ms 2864 KB Output is correct
18 Correct 43 ms 2892 KB Output is correct