Submission #687092

#	Time	Username	Problem	Language	Result	Execution time	Memory
687092		GudStonks	K blocks (IZhO14_blocks)	C++17	100 / 100	243 ms	81468 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ft first
#define sd second
const ll MOD = 1e9+7;
ll n, k, arr[100005], dp[100005][101];
void fun(){
	memset(arr, 0x3f, sizeof(arr));
	cin>>n>>k;
	for(int i = 1; i <= n; i++)cin>>arr[i];
	for(int i = 1; i <= n; i++)dp[i][1] = max(arr[i], dp[i - 1][1]);
	for(int j = 2; j <= k; j++){
		stack<pair<ll, ll> >st;
		for(int i = j; i <= n - (k - j); i++){
			ll x = dp[i - 1][j - 1];
			while(!st.empty() && arr[st.top().ft] <= arr[i]){
				x = min(x, st.top().sd);
				st.pop();
			}
			dp[i][j] = min(x + arr[i], (!st.empty() ? dp[st.top().ft][j] : (ll)2e18));
			st.push({i, x});
		}
	}
	cout<<dp[n][k];
}

int  main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int ttt = 1;
	//cin>>ttt;
	while(ttt--)fun();
}

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