Submission #1092073

#TimeUsernameProblemLanguageResultExecution timeMemory
1092073juicyK blocks (IZhO14_blocks)C++17
100 / 100
104 ms159904 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif const int N = 1e5 + 5, K = 101; int n, k; int a[N]; long long dp[N][K], f[N][K]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> k; for (int i = 1; i <= n; ++i) { cin >> a[i]; } memset(f, 0x3f, sizeof(f)); memset(dp, 0x3f, sizeof(dp)); dp[0][0] = 0; vector<int> st; for (int i = 1; i <= n; ++i) { for (int j = 0; j <= k; ++j) { f[i][j] = dp[i - 1][j]; } while (st.size() && a[st.back()] <= a[i]) { for (int j = 0; j <= k; ++j) { f[i][j] = min(f[i][j], f[st.back()][j]); } st.pop_back(); } for (int j = 1; j <= k; ++j) { dp[i][j] = min(dp[i][j], f[i][j - 1] + a[i]); } if (st.size()) { for (int j = 1; j <= k; ++j) { dp[i][j] = min(dp[i][j], dp[st.back()][j]); } } st.push_back(i); } cout << dp[n][k]; 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...