Submission #343681

#TimeUsernameProblemLanguageResultExecution timeMemory
343681_aniK blocks (IZhO14_blocks)C++17
100 / 100
656 ms82788 KiB
#define BUGO(x) cerr << #x << " = " << (x) << '\n'; #include <iostream> #include <algorithm> #include <stack> #include <vector> using namespace std; using ll = long long; const int N = 100'002; const int K = 20; const ll inf = 1'000'000'000'000'000'000LL; ll dp[N][102], a[N]; struct el { ll x; int ind; }; bool operator<(const el& a, const el& b) { return a.x < b.x; } int main() { ios_base::sync_with_stdio(false); cin.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++) for (int curk = 1; curk <= k; curk++) dp[i][curk] = inf; for (int curk = 1; curk <= k; curk++) { stack<el> x; vector<int> mn; x.push({ inf, 0 }); for (int i = 1; i <= n; i++) { while (!mn.empty() && dp[mn.back()][curk - 1] > dp[i - 1][curk - 1]) mn.erase(prev(mn.end())); if (i > 1) mn.push_back(i - 1); while (x.top().x < a[i])x.pop(); el prev = x.top(); x.push({ a[i], i }); if (i < curk) { continue; } if (curk == 1) dp[i][curk] = ((i - 1 != 0) ? max(dp[i - 1][1], a[i]) : a[i]); else if (prev.ind == 0) { if (i - 1 == 0) dp[i][curk] = a[i]; else { int x = lower_bound(mn.begin(), mn.end(), 1) - mn.begin(); // cerr << x << '\n'; dp[i][curk] = a[i] + dp[mn[x]][curk - 1]; } } else { int x = lower_bound(mn.begin(), mn.end(), prev.ind) - mn.begin(); // cerr << x << '\n'; dp[i][curk] = min(dp[prev.ind][curk], dp[mn[x]][curk - 1] + a[i]); } } } /* for (int i = 0; i <= n; i++) { for (int curk = 0; curk <= k; curk++) cerr << dp[i][curk] << ' '; cerr << '\n'; }*/ cout << dp[n][k] << '\n'; 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...