Submission #645255

#	Time	Username	Problem	Language	Result	Execution time	Memory
645255		someone	K blocks (IZhO14_blocks)	C++14	100 / 100	266 ms	82364 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], dp[K][N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n >> k;
    n++;
    for(int i = 1; i < n; i++)
        cin >> a[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;
        vector<pair<int, int>> imax;
        a[i-1] = INF;
        imax.push_back({i-1, INF});
        for(int j = i; j < n; j++) {
            int mini = dp[i-1][j-1];
            while(a[imax.back().first] <= a[j]) {
                mini = min(mini, imax.back().second);
                imax.pop_back();
            }
            dp[i][j] = min(a[j] + mini, dp[i][max(imax.back().first, i-1)]);
            imax.push_back({j, mini});
        }
    }
    cout << dp[k][n-1];
}

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