Submission #600446

#	Time	Username	Problem	Language	Result	Execution time	Memory
600446		verngutz	Discharging (NOI20_discharging)	C++17	36 / 100	1088 ms	100036 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 T> struct monoid {
    const T identity;
    const function<T(T, T)> combine;
};
template <typename T> struct sparse_table {
    const int size;
    const monoid<T> m;
    vector<vector<T>> st;
    sparse_table(const vector<T>& a, const monoid<T>& m)
    : size(a.size()), m(m), st(__lg(size) + 1, vector<T>(size, m.identity)) {
        st[0] = a;
        for(int pow2 = 1; pow2 <= __lg(size); pow2++) {
            for(int i = 0; i + (1 << pow2) - 1 < size; i++) {
                st[pow2][i] = m.combine(st[pow2 - 1][i], st[pow2 - 1][i + (1 << (pow2 - 1))]);
            }
        }
    }
    T query(int L, int R, bool inclusive) {
        assert(L < R + inclusive);
        R += inclusive;
        return m.combine(st[__lg(R - L)][L], st[__lg(R - L)][R - (1 << __lg(R - L))]);
    }
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> t(n);
    cin >> t;
    sparse_table<int> st(t, {lim<int>::min(), [](int x, int y) { return max(x, y); }});
    vector<ll> opt(n + 1);
    for(int i = n; i >= 0; i--) {
        if(i == n) {
            opt[i] = 0;
        } else {
            opt[i] = lim<ll>::max();
            for(int j = i + 1; j <= n; j++) {
                opt[i] = min(opt[i], st.query(i, j, false) * ll(n - i) + opt[j]);
            }
        }
    }
    cout << opt[0] << endl;
    return 0;
}

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