Submission #430982

#	Time	Username	Problem	Language	Result	Execution time	Memory
430982		haxorman	K blocks (IZhO14_blocks)	C++14	53 / 100	10 ms	10188 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

const int mxN = 107;
const int mxV = 1e6 + 7;
const int INF = 1e9 + 7;

int n, arr[mxN], dp[mxN][mxN][mxN], conv[mxV], unconv[mxN];

int rec(int i, int k, int prev_max) {
	if (i > n) {
		return (!k ? 0 : INF);
	}

	if (i <= n && !k) {
		return INF;
	}

	prev_max = max(prev_max, arr[i]);
	if (dp[i][k][prev_max] != -1) {
		return dp[i][k][prev_max];
	}


	int choose = rec(i + 1, k - 1, 0) + unconv[prev_max];
	int skip = rec(i + 1, k, prev_max);

	dp[i][k][prev_max] = min(choose, skip);
	return min(choose, skip); 
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    memset(dp, -1, sizeof(dp));

    int k;
    cin >> n >> k;

    vector<int> vec;
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
		vec.push_back(arr[i]);
	}
	sort(vec.begin(), vec.end());

	int ind = 1;
	for (int i = 0; i < n; ++i) {
		if (!conv[vec[i]]) {
			conv[vec[i]] = ind++;
		}
	}
	assert(ind < 107);

	for (int i = 1; i <= n; ++i) {
		unconv[conv[arr[i]]] = arr[i];
		arr[i] = conv[arr[i]];
	}

	cout << rec(1, k, 0) << "\n";
}

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