Submission #312248

#	Time	Username	Problem	Language	Result	Execution time	Memory
312248		tevdore	K blocks (IZhO14_blocks)	C++14	100 / 100	389 ms	81400 KiB

blocks

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N = 1e5 + 10;
ll n, k, mn, m;
ll a[N], dp[N][101];
stack < pair < ll, ll > > s;
main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) dp[i][1] = max(a[i], dp[i - 1][1]);
    for(int i = 2; i <= k; i++) {
        while(!s.empty()) s.pop();
        for(int j = i; j <= n; j++) {
            m = 1e18;
            mn = dp[j - 1][i - 1];
            while(!s.empty() && s.top().second <= a[j]) {
                mn = min(mn, s.top().first);
                s.pop();
            }
            if(!s.empty()) m = s.top().first + s.top().second;
            dp[j][i] = min(mn + a[j], m);
            if(s.empty() || m >= a[j] + mn) s.push({mn, a[j]});
        }
    }
    cout << dp[n][k] << "\n";
}

Compilation message (stderr)

blocks.cpp:8:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main() {
      |      ^

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