Submission #1191034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191034		peteza	K blocks (IZhO14_blocks)	C++20	0 / 100	0 ms	328 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

int n, k;
int dp[2][200005];
int arr[200005];
int sps[20][200005];

int fmx(int l, int r) {
    int dist = 31 - __builtin_clz(r-l+1);
    //cout << dist << ' ' << l << " and " << r << '\n';
    return max(sps[dist][l], sps[dist][r-(1<<dist)+1]);
}

void dcdp(int l, int r, int tl, int tr, int cmode) {
    if(l > r) return;
    pair<int, int> opt(1999999999, -1);
    int mid = (l+r) >> 1;
    for(int i=tl;i<=min(tr, mid);i++) {
        opt = min(opt, {dp[cmode^1][i-1] + fmx(i, mid), i});
    }
    dp[cmode][mid] = opt.first;
    dcdp(l, mid-1, tl, opt.second, cmode);
    dcdp(mid+1, r, opt.second, tr, cmode);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1;i<=n;i++) dp[0][i] = 1999999999;
    for(int i=1;i<=n;i++) {cin >> arr[i]; sps[0][i] = arr[i];}
    for(int k=1;k<20;k++) {
        for(int i=1;i+(1<<(k-1))<=n;i++) {
            sps[k][i] = max(sps[k-1][i], sps[k-1][i+(1<<(k-1))]);
            //cout << sps[k][i] << ' ';
        }
        //cout << '\n';
    }
    //while(1) {int a, b; cin >> a >> b; cout << fmx(a, b) << '\n';}
    for(int ck=1;ck<=k;ck++) {
        for(int i=0;i<=n;i++) dp[ck&1][i] = 1999999999;
        dcdp(1, n, 1, n, ck&1);
    }
    cout << dp[k&1][n];
}

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