제출 #835806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
835806		elkernos	Building Bridges (CEOI17_building)	C++17	100 / 100	62 ms	8972 KiB

building

// 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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40