Submission #885122

#TimeUsernameProblemLanguageResultExecution timeMemory
885122votranngocvyK blocks (IZhO14_blocks)C++14
100 / 100
134 ms84736 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair const int N = 1e5 + 5; const int inf = 0x3f3f3f3f3f3f3f3f; int a[N],n,k,dp[105][N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i <= k; i++) for (int j = 0; j <= n; j++) dp[i][j] = inf; int Max = 0; for (int i = 1; i <= n; i++) { Max = max(Max,a[i]); dp[1][i] = Max; } for (int i = 2; i <= k; i++) { stack<pii>st; for (int j = 1; j <= n; j++) { int Min = dp[i - 1][j - 1]; while (!st.empty() && a[st.top().fi] < a[j]) { Min = min(Min,st.top().se); st.pop(); } if (st.empty() || a[j] + Min < a[st.top().fi] + st.top().se) st.push(mp(j,Min)); if (j >= i) dp[i][j] = a[st.top().fi] + st.top().se; } } cout << dp[k][n] << "\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...