Submission #345198

#TimeUsernameProblemLanguageResultExecution timeMemory
345198_zheksenovK blocks (IZhO14_blocks)C++14
53 / 100
2 ms752 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e3 + 5; const int INF = 1e9 + 7; int a[N], dp[N][N]; signed 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 j = 0; j <= k; j++) dp[i][j] = INF; dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= min(i, k); j++) { int mx = a[i]; for (int x = i - 1; x >= 0; x--) { dp[i][j] = min(dp[i][j], dp[x][j - 1] + mx); mx = max(a[x], mx); } } } cout << dp[n][k] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...