Submission #908783

#	Time	Username	Problem	Language	Result	Execution time	Memory
908783		khachatur25	K blocks (IZhO14_blocks)	C++14	100 / 100	180 ms	84496 KiB

blocks

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

const int N = 1e5 + 5;

int v[N], dp[105][N];
int n,k,x,mx;

signed main() {
    ios_base::sync_with_stdio(false);
    cin >> n >> k;
    v[0] = 1e9;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        mx = max(mx, v[i]);
        dp[1][i] = mx;
    }
    for (int i = 2; i <= k; i++) {
        stack<pair<int, int>> s;
        for (int j = i; j <= n; j++) {
            int vl = dp[i - 1][j - 1];
            while (!s.empty() && s.top().first <= v[j])vl = min(vl, s.top().second), s.pop();
            dp[i][j] = vl + v[j];

            if (!s.empty())dp[i][j] = min(dp[i][j], s.top().first + s.top().second);

            // Update the stack
            if (s.empty())s.push({v[j], vl});
            else if (s.top().first + s.top().second > v[j] + vl)s.push({v[j], vl});
        }
    }
    cout << dp[k][n];
}

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