Submission #343653

#TimeUsernameProblemLanguageResultExecution timeMemory
343653_aniK blocks (IZhO14_blocks)C++17
53 / 100
1106 ms135332 KiB
#define BUGO(x) cerr << #x << " = " << (x) << '\n'; #include <iostream> #include <algorithm> #include <stack> using namespace std; using ll = long long; ll inf = 1'000'000'000'000'000'000LL; ll dp[100'002][102], a[100'002]; ll mn[4 * 100'002][102]; struct el { ll x; int ind; }; bool operator<(const el& a, const el& b) { return a.x < b.x; } void Add(int v, int vl, int vr, int k, int pos) { if (vl == vr) { mn[v][k] = dp[pos][k]; return; } int m = (vl + vr) / 2; if (pos <= m) Add(v * 2, vl, m, k, pos); else Add(v * 2 + 1, m + 1, vr, k, pos); mn[v][k] = min(mn[v * 2][k], mn[v * 2 + 1][k]); } ll Mn(int v, int vl, int vr, int k, int l, int r) { if (vl == l && vr == r) { return mn[v][k]; } int m = (vl + vr) / 2; ll res = inf; if (l <= m) res = min(res, Mn(v * 2, vl, m, k, l, min(r, m))); if (r > m) res = min(res, Mn(v * 2 + 1, m + 1, vr, k, max(l, m + 1), r)); return res; } int main() { 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; x.push({ inf, 0 }); for (int i = 1; i <= n; i++) { while (x.top().x < a[i])x.pop(); el prev = x.top(); x.push({ a[i], i }); if (i < curk) { Add(1, 1, n, curk, i); continue; } if (curk == 1) dp[i][curk] = ((i - 1 != 0) ? max(dp[i - 1][1], a[i]) : a[i]); else if (prev.ind == 0) { dp[i][curk] = ((i - 1 == 0) ? 0 : Mn(1, 1, n, curk - 1, 1, i - 1)) + a[i]; } else dp[i][curk] = min(dp[prev.ind][curk], Mn(1, 1, n, curk - 1, prev.ind, i - 1) + a[i]); Add(1, 1, n, curk, 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...