Submission #1090465

#TimeUsernameProblemLanguageResultExecution timeMemory
1090465hoangnguyenhK blocks (IZhO14_blocks)C++14
100 / 100
110 ms43372 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const int K = 105; const int INF = 0x3f3f3f3f; int a[N], L[N], minF[N]; int dp[K][N]; int n, k; int main() { cin >> n >> k; for (int i = 1; i <= n; ++i) cin >> a[i]; memset(dp, 0x3f, sizeof dp); dp[1][0] = 0; for (int i = 1; i <= n; ++i) dp[1][i] = max(dp[1][i - 1], a[i]); for (int i = 1; i <= n; ++i) for (L[i] = i - 1; L[i] && a[L[i]] <= a[i]; ) L[i] = L[L[i]]; for (int i = 2; i <= k; ++i) { minF[i - 1] = INF; for (int j = i; j <= n; ++j) { minF[j] = dp[i - 1][j - 1]; for (int t = j - 1; t > L[j]; t = L[t]) minF[j] = min(minF[j], minF[t]); dp[i][j] = min(dp[i][L[j]], minF[j] + a[j]); } } 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...