Submission #1218773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218773		Johan	K blocks (IZhO14_blocks)	C++20	18 / 100	2 ms	328 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
const int N = 1e2;
int a[N], st[N * 4], dp[N][N];
void build(int v, int l, int r){
	if(l == r){
		st[v] = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(v * 2, l, mid);
	build(v * 2 + 1, mid + 1, r);
	st[v] = max(st[v * 2], st[v * 2 + 1]);
}
int ask(int v, int l, int r, int ql, int qr){
	if(l > qr || r < ql)return -1e9;
	if(l >= ql && r <= qr)return st[v];
	int mid = (l + r) >> 1;
	return max(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr));
}
int main(){
	int n, k_;
	cin >> n >> k_;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 0; i <= n; i++){
		for(int k = 0; k <= k_; k++){
			dp[i][k] = 1e9;
		}
	}
	dp[0][0] = 0;
	build(1, 1, n);
	for(int k = 1; k <= k_; k++){
		for(int i = 1; i <= n; i++){
			for(int j = i - 1; j >= 0; j--){
				dp[i][k] = min(dp[i][k], dp[j][k - 1] + ask(1, 1, n, j + 1, i));
			}
		}
	}
	cout << dp[n][k_] << endl;
}

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