Submission #834274

#	Time	Username	Problem	Language	Result	Execution time	Memory
834274		vjudge1	K blocks (IZhO14_blocks)	C++17	100 / 100	209 ms	44708 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second

int N, K;
int A[100100];
int dp[100100][110];
stack<pii> st;
int maks;

// dp[n][1] = max(a[1..n]);

int main () {
	cin >> N >> K;
	for(int i=1; i<=N; i++) {
		cin >> A[i];
		maks = max(maks, A[i]);
		dp[i][1] = maks;
	}
	
	for(int k=2; k<=K; k++) {
		while(!st.empty()) st.pop();
		for(int n=1; n<=N; n++) {
			if (n<k) dp[n][k] = 1e9;
			else {
				int mins = dp[n-1][k-1];
				while(!st.empty() && A[st.top().fi] <= A[n]) {
					mins = min(mins, st.top().se);
					st.pop();
				}
				dp[n][k] = mins+A[n];
				if (!st.empty())
					dp[n][k] = min(dp[n][k], dp[st.top().fi][k]);
				st.push({n,mins});
			}
		}
	}
	cout << dp[N][K] << endl;
}

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