Submission #917026

#	Time	Username	Problem	Language	Result	Execution time	Memory
917026		atom	K blocks (IZhO14_blocks)	C++17	0 / 100	16 ms	86872 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 = 17;
const int M = 105;

int rmq[K][N];
int lg[N];
int get(int l, int r) {
    int k = lg[r - l + 1];
    return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
}
int n, m;
int a[N];
ll dp[M][N];

void solve(int x, int l, int r, int opt_l, int opt_r) {
    if (l > r) return;
    int mi = (l + r) >> 1;
    ll ans = 1e18;
    int split = -1;
    for (int i = opt_l; i <= min(mi, opt_r); ++i) {
        ll curAns = dp[x - 1][i] + get(i + 1, mi);
        if (curAns < ans) {
            ans = curAns;
            split = i;
        }
    }
    dp[x][mi] = ans;
    solve(x, l, mi - 1, opt_l, split);
    solve(x, mi + 1, r, split, opt_r);
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    for (int i = 1; i <= n; ++i) rmq[0][i] = a[i];
    for (int k = 1; k < K; ++k) {
        int step = 1 << (k - 1);
        for (int i = 1; i + step <= n; ++i)
            rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + step]);
    }

    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; ++i) {
        dp[1][i] = get(1, i);
        // debug(dp[1][i]);
    }
    for (int i = 2; i <= m; ++i) {  
        solve(i, 1, n, 1, n);
        // for (int j = 1; j <= n; ++j) {
        //     debug(dp[i][j]);
        // }
    }
    cout << dp[m][n] << "\n";
}

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