Submission #430839

#TimeUsernameProblemLanguageResultExecution timeMemory
430839haxormanK blocks (IZhO14_blocks)C++14
0 / 100
3 ms5068 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...