Submission #430878

#	Time	Username	Problem	Language	Result	Execution time	Memory
430878		faresbasbs	K blocks (IZhO14_blocks)	C++14	100 / 100	219 ms	41240 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
int n,k,arr[100001],dp[101][100001];

int main(){
	cin >> n >> k;
	for(int i = 0 ; i <= k ; i += 1){
		for(int j = 0 ; j <= n ; j += 1){
			dp[i][j] = 1000000000;
		}
	}
	int mx = 0;
	for(int i = 1 ; i <= n ; i += 1){
		cin >> arr[i];
		mx = max(mx,arr[i]);
		dp[1][i] = mx;
	}
	for(int i = 2 ; i <= k ; i += 1){
		stack<int> st1,st2;
		for(int j = 1 ; j <= n ; j += 1){
			int best = dp[i-1][j-1];
			while(st1.size() && st1.top() < arr[j]){
				best = min(best,st2.top());
				st1.pop(),st2.pop();
			}
			if(!st1.size() || best+arr[j] < st1.top()+st2.top()){
				st1.push(arr[j]),st2.push(best);
			}
			if(j >= i){
				dp[i][j] = st1.top()+st2.top();
				// cout << i << " " << j << " " << dp[i][j] << " " << st1.top() << " " << st2.top() << endl;
			}
		}
	}
	cout << dp[k][n] << endl;
}

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