Submission #647604

#	Time	Username	Problem	Language	Result	Execution time	Memory
647604		Tam_theguide	K blocks (IZhO14_blocks)	C++14	100 / 100	233 ms	43212 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int K = 105;
const int INF = 1e9;
using pii = pair<int, int>;
#define fi first
#define se second
int n, a[N], k, dp[N][K], l[N];
void cmin(int& x, int y){x = min(x, y);}
int main(){
    //freopen("kblocks.inp", "r", stdin);
    //freopen("kblocks.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= k; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for (int j = 1; j <= k; j++){
        stack<pii> st;
        for (int i = j; i <= n; i++){
            int mn = dp[i - 1][j - 1];
            while (!st.empty() && a[st.top().se] <= a[i]){
                cmin(mn, st.top().fi);
                st.pop();
            }
            if (st.empty()) l[i] = 0;
            else l[i] = st.top().se;
            st.emplace(mn, i);
            dp[i][j] = min(dp[l[i]][j], mn + a[i]);
        }
    }
    cout << dp[n][k];
}

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