Submission #1257955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257955		goldenbull	K blocks (IZhO14_blocks)	C++17	53 / 100	1096 ms	1092 KiB

blocks

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

const char el = '\n';
const int maxn = 1e6+7;
const int logn = 21;
const ll inf = 1e16+7;

int n, k;
int a[maxn];
int spt[logn][maxn];

ll dp[2][maxn];

template<typename T>
void print(T a[], int n) { for (int i = 0; i < n; i++) cout << a[i] << ' '; cout << el; }

void build_spt() {
    for (int i = 1; i <= n; i++) spt[0][i] = a[i];
    for (int i = 1; i < logn; i++) {
        int p = 1<<i;
        int q = p>>1;
        if (p > n) break;
        for (int j = 1; j+p-1 <= n; j++) {
            int a = spt[i-1][j];
            int b = spt[i-1][j+q];
            spt[i][j] = max(a, b);
        }
    }
}

int get(int l, int r) {
    if (l > r) swap(l, r);
    int k = __lg(r-l+1);
    int a = spt[k][l];
    int b = spt[k][r-(1<<k)+1];
    return max(a, b);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
//    freopen("test.inp", "r", stdin);
//    freopen(".inp", "r", stdin);
//    freopen(".out", "w", stdout);

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

    build_spt();
    for (int i = 0; i<2; i++) fill(dp[i], dp[i]+n+1, inf);

    int c = 1;

    dp[c&1][0] = 0;
    for (int i = 1; i <= n; i++) dp[c&1][i] = get(1, i);

    c++;
    for (; c <= k; c++) {
        int cur = c&1, prev = cur^1;
        fill(dp[cur], dp[cur]+n+1, inf);
        dp[cur][0] = 0;
        for (int i = 1; i <= c; i++) dp[cur][i] = dp[cur][i-1] + a[i];

        for (int i = c+1; i <= n; i++)
            for (int j = i; j >= c; j--)
                dp[cur][i] = min(dp[cur][i], get(i, j) + dp[prev][j-1]);
    }
    cout << dp[k&1][n];

    return 0;
}

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