Submission #1101484

#TimeUsernameProblemLanguageResultExecution timeMemory
1101484TPhatK blocks (IZhO14_blocks)C++17
53 / 100
1059 ms82512 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int long long #define INF 1000000000 int n, k; int a[100005]; int dp[105][100005]; signed main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { dp[1][i] = a[i]; for (int j = 1; j < i; j++) { dp[1][i] = max(dp[1][i], a[j]); } } for (int i = 2; i <= k; i++) { for (int j = i; j <= n; j++) { int max_val = 0; dp[i][j] = INF; for (int l = j; l >= i; l--) { max_val = max(max_val, a[l]); dp[i][j] = min(dp[i][j], dp[i-1][l-1] + max_val); } } } cout << dp[k][n] << endl; 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...