Submission #1267101

#TimeUsernameProblemLanguageResultExecution timeMemory
1267101canhnam357K개의 묶음 (IZhO14_blocks)C++20
100 / 100
167 ms1912 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n); for (int &i : a) cin >> i; auto dp = a; for (int i = 1; i < n; i++) dp[i] = max(dp[i - 1], dp[i]); const int inf = 1e9; auto new_dp = dp; for (int _ = 1; _ < k; _++) { for (int i = 0; i < n; i++) new_dp[i] = inf; stack<int> s, t; for (int i = 0; i < n; i++) { int mx = inf; while (!s.empty() && a[s.top()] <= a[i]) { mx = min(mx, t.top()); t.pop(); s.pop(); } new_dp[i] = min(new_dp[i], mx + a[i]); if (!s.empty()) { new_dp[i] = min(new_dp[i], dp[s.top()] + a[i]); new_dp[i] = min(new_dp[i], new_dp[s.top()]); } mx = min(mx, dp[i]); s.push(i); t.push(mx); } swap(dp, new_dp); } cout << dp[n - 1]; 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...