Submission #1180402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180402		altern23	K blocks (IZhO14_blocks)	C++17	100 / 100	120 ms	4944 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 1e6;
const ll INF = 4e18;
const int MOD = 998244353;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;		
	for(;tc--;){
		ll N, K; cin >> N >> K;
		vector<ll> a(N + 5), lf(N + 5, 1), rg(N + 5, N);
		for(int i = 1; i <= N; i++) cin >> a[i];

		vector<ll> dp(N + 5, INF);
		dp[0] = 0;
		for(int i = 1; i <= K; i++){
			stack<pii> stk;
			vector<ll> ndp(N + 5, INF);
			for(int j = 1; j <= N; j++){
				ll cur = dp[j - 1];
				while(!stk.empty() && a[stk.top().fi] <= a[j]){
					cur = min(cur, stk.top().sec);
					stk.pop();
				}
				// bikin segment baru
				ndp[j] = cur + a[j];
				// gabung dengan segment sebelumnya
				if(!stk.empty()) ndp[j] = min(ndp[j], ndp[stk.top().fi]);
				stk.push({j, cur});
			}
			dp.swap(ndp);
		}
		
		cout << dp[N] << "\n";
	}
}

/*
1 2 3 4 5 6 7
*/

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