Submission #917067

#	Time	Username	Problem	Language	Result	Execution time	Memory
917067		atom	K blocks (IZhO14_blocks)	C++17	100 / 100	130 ms	84504 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) {
        x += n;
        f[x] = merge(f[x], 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];
    
    

    // 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);
    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    for (int i = 1; i <= n; ++i)
        dp[1][i] = max(dp[1][i - 1], 1LL * a[i]);

    for (int _k = 2; _k <= k; ++_k) {
        stack <pair <ll, int>> S;
        for (int i = _k; i <= n; ++i) {
            ll p = dp[_k - 1][i - 1];
            while (!S.empty() && a[i] >= a[S.top().second]) {
                p = min(p, S.top().first);
                S.pop();
            }
            int j = S.empty()? 0 : S.top().second;
            dp[_k][i] = min(dp[_k][j], p + a[i]);
            S.push({p, i});
        }
    }
    cout << dp[k][n] << "\n";
}

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