oj.uz

Submission #430839

# Submission time Handle Problem Language Result Execution time Memory
430839 2021-06-17T06:58:24 Z haxorman K blocks (IZhO14_blocks) C++14
0 / 100
 3 ms 5068 KB 
#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];

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

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

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

	prev_max = max(prev_max, arr[i]);

	int choose = rec(i + 1, k - 1, 0) + 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++;
		}
	}

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

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Incorrect 3 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Incorrect 3 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Incorrect 3 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5068 KB Output is correct
2 Incorrect 3 ms 5068 KB Output isn't correct
3 Halted 0 ms 0 KB -