Submission #1122752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122752		Tsagana	K blocks (IZhO14_blocks)	C++20	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;

struct mlp {int d[101];};

mlp dp[100001];
mlp ds[100001];

void solve () {
	int n, k; cin >> n >> k;
	
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		
		dp[i].d[1] = ds[i].d[1] = max(ds[i-1].d[1], x);

		for (int j = 2; j < i; j++) {
			if (dp[i-1].d[j-1] + x <=
				dp[i-1].d[j] + max(ds[i-1].d[j], x) - min(ds[i-1].d[j], x)) {
				
				dp[i].d[j] = dp[i-1].d[j-1] + x;
				ds[i].d[j] = x;
			}
			else {
				ds[i].d[j] = max(ds[i-1].d[j], x);
				int mn = min(ds[i-1].d[j], x);
				dp[i].d[j] = dp[i-1].d[j] + ds[i].d[j] - mn;
			}

		}

		dp[i].d[i] = dp[i-1].d[i-1] + x;
		ds[i].d[i] = x;
	}
	cout << dp[n].d[k];
}
signed main() {IOS solve(); return 0;}

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