Submission #863897

#	Time	Username	Problem	Language	Result	Execution time	Memory
863897		phongcd	K blocks (IZhO14_blocks)	C++14	100 / 100	126 ms	41840 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;
 
int n, k;
int a[N], f[N][102];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> k;
    for (int i = 1; i <= n; i ++) cin >> a[i];

    memset(f, 0x3f3f, sizeof f);

    f[0][1] = 0;
    for (int i = 1; i <= n; i ++) 
        f[i][1] = max(f[i - 1][1], a[i]);

    for (int j = 2; j <= k; j ++) {
        stack <ii> h;
        for (int i = j; i <= n; i ++) {
            int cur = f[i - 1][j - 1];
            while (!h.empty() && a[h.top().se] <= a[i]) {
                cur = min(cur, h.top().fi);
                h.pop();
            }
            f[i][j] = min(f[(h.empty() ? 0 : h.top().se)][j], cur + a[i]);
            h.push({cur, i});
        } 
    }
    cout << f[n][k];
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

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