Submission #645246

#	Time	Username	Problem	Language	Result	Execution time	Memory
645246		someone	K blocks (IZhO14_blocks)	C++14	0 / 100	1 ms	1108 KiB

blocks

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

const int N = 1e5 + 42, K = 110, INF = 1e15 + 42;

int n, k, a[N], pre[N], dp[K][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    n++;
    a[0] = INF;
    vector<int> imax(1);
    for(int i = 1; i < n; i++) {
        cin >> a[i];
        while(a[imax.back()] < a[i])
            imax.pop_back();
        pre[i] = imax.back();
        imax.push_back(i);
    }
    for(int i = 1; i < N; i++)
        dp[0][i] = INF;
    for(int i = 1; i <= k; i++) {
        for(int j = 0; j < n; j++)
            dp[i][j] = INF;
        for(int j = i; j < n; j++)
            dp[i][j] = min(a[j] + dp[i-1][max(pre[j], i-1)], dp[i][max(pre[j], i-1)]);
    }
    cout << dp[k][n-1];
}

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