Submission #333845

#	Time	Username	Problem	Language	Result	Execution time	Memory
333845		limabeans	K blocks (IZhO14_blocks)	C++17	100 / 100	219 ms	80636 KiB

blocks

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const int maxn = 100000 + 10;
const ll inf = 1e10;

int n,k;
ll a[maxn];
ll dp[102][maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    for (int i=1; i<=n; i++) {
	dp[1][i]=max(a[i],dp[1][i-1]);
    }


    

    for (int j=2; j<=k; j++) {
	stack<pair<int,ll>> stk;
	for (int i=j; i<=n; i++) {
	    ll mindp = dp[j-1][i-1];
	    while (!stk.empty() && a[stk.top().first] <= a[i]) {
		mindp = min(mindp, stk.top().second);
		stk.pop();
	    }
	    dp[j][i] = min(mindp+a[i], stk.empty() ? inf : dp[j][stk.top().first]);
	    stk.push({i,mindp});
	}
    }


    cout<<dp[k][n]<<endl;    
    return 0;
}

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