Submission #600465

#	Time	Username	Problem	Language	Result	Execution time	Memory
600465		verngutz	Discharging (NOI20_discharging)	C++17	100 / 100	183 ms	37104 KiB

Discharging

#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
template <typename Iter, typename T> int gt(Iter L, Iter R, T v) { return upper_bound(L, R, v) - L; }
template <typename Iter, typename T> int ge(Iter L, Iter R, T v) { return lower_bound(L, R, v) - L; }
template <typename Iter, typename T> int lt(Iter L, Iter R, T v) { return lower_bound(L, R, v) - L - 1; }
template <typename Iter, typename T> int le(Iter L, Iter R, T v) { return upper_bound(L, R, v) - L - 1; }
template <typename Bst, typename T> typename Bst::const_iterator gt(const Bst& bst, T v) { return bst.upper_bound(v); }
template <typename Bst, typename T> typename Bst::const_iterator ge(const Bst& bst, T v) { return bst.lower_bound(v); }
template <typename Bst, typename T> typename Bst::const_iterator lt(const Bst& bst, T v) { return bst.lower_bound(v) == bst.begin() ? bst.end() : --bst.lower_bound(v); }
template <typename Bst, typename T> typename Bst::const_iterator le(const Bst& bst, T v) { return bst.upper_bound(v) == bst.begin() ? bst.end() : --bst.upper_bound(v); }
// maintain an upper/lower hull L of lines y = mx + b
// query for y(x) such that y(x) is minimum/maximum over all lines y in L
// assumes lines are inserted in non-increasing/non-decreasing order of m
// minimization by default, call constructor with greater<ll>() for maximization
struct cht {
    struct line {
        ll m, b, intersection;
        ll eval(ll x) const { return m * x + b; }
        ll cross(const line& l) const { return (l.b - b) / (m - l.m); }
        bool operator<(const line& l) const { return m > l.m; }
        bool operator<(const ll x) const { return intersection < x; }
        friend bool operator<(const ll x, const line& l) { return x < l.intersection; }
    };
    multiset<line, less<>> h;
    const function<bool(ll, ll)> cmp;
    cht(const function<bool(ll, ll)>& cmp = less<ll>()) : cmp(cmp) {}
    const line& l1() { return *h.rbegin(); }
    const line& l2() { return *++h.rbegin(); }
    void pop() { h.erase(--h.end()); }
    void add(ll m, ll b) {
        if(h.empty()) {
            h.insert({m, b, numeric_limits<ll>::min()});
        } else if(m != l1().m or cmp(b, l1().b)) {
            if(m == l1().m) pop();
            while(h.size() >= 2 and l1().cross({m, b}) <= l1().cross(l2())) pop();
            h.insert({m, b, l1().cross({m, b})});
        }
    }
    ll opt(ll x) {
        assert(!h.empty());
        ll y1 = lt(h, x)->eval(x), y2 = le(h, x)->eval(x);
        return cmp(y1, y2) ? y1 : y2;
    }
};
template <typename T, typename Cmp = decltype(less<T>())>
vector<int> nsv(const vector<T>& a, int L, int R, int d, Cmp&& cmp = less<T>()) {
    static_assert(is_convertible<decltype(cmp), function<bool(T, T)>>::value);
    vector<int> s, nearest_smaller_to(a.size());
    for(int i = L; i != R; i += d) {
        while(not s.empty() and not cmp(a[s.back()], a[i])) {
            s.pop_back();
        }
        nearest_smaller_to[i] = s.empty() ? L - d : s.back();
        s.push_back(i);
    }
    return nearest_smaller_to;
}
template <typename T, typename Cmp = decltype(less<T>())>
vector<int> lnsv(const vector<T>& a, Cmp&& cmp = less<T>()) {
    return nsv(a, 0, a.size(), 1, cmp);
}
template <typename T, typename Cmp = decltype(less<T>())>
vector<int> rnsv(const vector<T>& a, Cmp&& cmp = less<T>()) {
    return nsv(a, a.size() - 1, -1, -1, cmp);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<ll> t(n);
    cin >> t;
    auto lsv = lnsv(t);
    auto rgv = rnsv(t, greater<ll>());
    vector<ll> opt(n + 1);
    cht hull;
    vector<int> I;
    for(int i = 0; i < n; i = rgv[i]) {
        I.push_back(i);
    }
    I.push_back(n);
    for(int ii = I.size() - 1; ii >= 0; ii--) {
        int i = I[ii];
        if(i == n) {
            opt[i] = 0;
        } else {
            opt[i] = min(
                t[i] * (n - i) + opt[rgv[i]],
                hull.h.empty() ? lim<ll>::max() : hull.opt(n - i)
            );
        }    
        if(ii > 0) {
            hull.add(t[I[ii - 1]], opt[i]);
        }
    }
    cout << opt[0] << endl;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28