Submission #1125295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125295		Tsagana	K blocks (IZhO14_blocks)	C++17	0 / 100	0 ms	328 KiB

blocks

#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int n, k, mx;
int a[100001];
int dp[100001][101];
stack<pair<int, int>> st;

void solve () {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		mx = max(mx, a[i]);
		dp[i][1] = mx;
	}
	
	for (int i = 2; i <= k; i++) {
		while (!st.empty()) st.pop();
		
		for (int j = 1; j <= n; j++) {
			if (j < i) {dp[j][i] = 1e9; continue ;}

			int mn = dp[j-1][i-1];
			
			while (!st.empty() && a[st.top().F] <= a[n]) {mn = min(mn, st.top().S); st.pop();}
			
			dp[j][i] = mn + a[j];
			if (!st.empty()) dp[j][i] = min(dp[j][i], dp[st.top().F][i]);
			
			st.push({j, mn});
		}
	}

	cout << dp[n][k];
}
signed main() {IOS solve(); return 0;}

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