Submission #1248227

#TimeUsernameProblemLanguageResultExecution timeMemory
1248227votranngocvyK blocks (IZhO14_blocks)C++20
100 / 100
126 ms3884 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; const int inf = 1e18; int a[N],dp_before[N],dp_cur[N],curMin[N]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,k; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 0; i <= n; i++) dp_before[i] = dp_cur[i] = curMin[i] = inf; dp_before[0] = 0; for (int i = 1; i <= k; i++) { stack<int>s; for (int j = i; j <= n; j++) { curMin[j] = dp_before[j - 1]; while (!s.empty() && a[s.top()] <= a[j]) { curMin[j] = min(curMin[j],curMin[s.top()]); s.pop(); } if (s.empty()) dp_cur[j] = curMin[j] + a[j]; else dp_cur[j] = min(dp_cur[s.top()],curMin[j] + a[j]); s.push(j); } for (int j = 0; j <= n; j++) { dp_before[j] = dp_cur[j]; dp_cur[j] = curMin[j] = inf; } } cout << dp_before[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...