Submission #917035

#	Time	Username	Problem	Language	Result	Execution time	Memory
917035		atom	K blocks (IZhO14_blocks)	C++17	0 / 100	1 ms	4444 KiB

blocks

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
 
#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
 
const int N = 1e5 + 5;
const int K = 105;

template <typename T>
struct SegmentTree {
    vector <T> f;
    T NEUTRAL = numeric_limits <T>::max();
    int n;
    SegmentTree(int _n) { init(_n); }
    void init(int _n) {
        n = _n;
        f.resize((_n << 1) + 5, NEUTRAL);  
    }
    T merge(T x, T y) { return min(x, y); }
    void upd(int x, T val) {
        f[x += n] = val;
        for (; x > 0; x >>= 1)
            f[x >> 1] = merge(f[x], f[x ^ 1]);
    }
    T qry(int l, int r) {
        T ql = NEUTRAL;
        T qr = NEUTRAL;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) ql = merge(ql, f[l++]);
            if (r & 1) qr = merge(f[--r], qr);
        } 
        return merge(ql, qr);
    }
};

int n, k;
int a[N], lhs[N];
ll dp[K][N];
 
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
 
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    stack <int> S;
    for (int i = 1; i <= n; ++i) {
        while (!S.empty() && a[i] >= a[S.top()]) S.pop();
        lhs[i] = (S.empty()? 0 : S.top());
        S.push(i);
    }

    // dp(k, i) = min(dp(k - 1, j) + max(j..i));
    // j = lhs[i] + 1; -> dp(k, i) = a[i] + min(dp(k - 1, j)) (j : lhs[i] + 1 -> i);
    for (int _k = 1; _k <= k; ++_k) {
        SegmentTree <ll> st(n);
        for (int i = 1; i <= n; ++i) st.upd(i, dp[_k - 1][i]);
        for (int i = 1; i <= n; ++i)
            dp[_k][i] = a[i] + st.qry(lhs[i] + 1, i);
    }
    cout << dp[k][n] << "\n";
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47