Submission #1198110

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

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double	
  
const int MAX = 1e2 + 6;
const int LOG = 26;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int block = 320;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int dp[MAX][MAX][MAX], st[MAX * 4], a[MAX];
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 0;
	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));
}
void _(){
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)	
		cin >> a[i];
	build(1, 1, n);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= n - i; j++){
			for(int kk = 1; kk <= k; kk++){
				dp[i][j][kk] = inf;
			}
		}
	}
	dp[0][0][0] = 0;
	dp[1][0][1] = a[1];
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= n - i; j++){
			for(int kk = 1; kk <= k; kk++){
				int val = ask(1, 1, n, i, i + j);
				for(int z = i - 1; z >= 1; z--)
					dp[i][j][kk] = min(dp[i][j][kk], dp[z][i - 1 - z][kk - 1] + val);
			}
		}
	}
	int mn = inf;
	for(int i = 1; i <= n; i++)
		mn = min(mn, dp[i][n - i][k]);
	cout << mn << endl;
}
 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
//	cin >> t;
	while(t--)  _();
}

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