Submission #1083834

#TimeUsernameProblemLanguageResultExecution timeMemory
1083834f0rizenK blocks (IZhO14_blocks)C++17
0 / 100
1 ms460 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int inf = 1e9 + 7; const ll infll = 1e18; template<typename T> istream &operator>>(istream &is, vector<T> &a) { for (auto &i : a) { is >> i; } return is; } struct Tree { using Node = int; Node pull(const Node &a, const Node &b) { return min(a, b); } int n; vector<Node> t; Tree(int _n) : n(_n) { t.resize(4 * n, inf); } Node get(int v, int l, int r, int lq, int rq) { if (rq <= l || r <= lq) { return inf; } if (lq <= l && r <= rq) { return t[v]; } int mid = (l + r) / 2; return pull(get(2 * v + 1, l, mid, lq, rq), get(2 * v + 2, mid, r, lq, rq)); } int get(int l, int r) { return get(0, 0, n, l, r); } int get(int i) { return get(i, i + 1); } void upd(int v, int l, int r, int i, int x) { if (l + 1 == r) { t[v] = x; return; } int mid = (l + r) / 2; if (i < mid) { upd(2 * v + 1, l, mid, i, x); } else { upd(2 * v + 2, mid, r, i, x); } t[v] = pull(t[2 * v + 1], t[2 * v + 2]); } void upd(int i, int x) { upd(0, 0, n, i, x); } }; int32_t main() { #ifdef LOCAL freopen("/tmp/input.txt", "r", stdin); #else ios::sync_with_stdio(false); cin.tie(nullptr); #endif int n, k; cin >> n >> k; vector<int> a(n); cin >> a; vector<int> l(n); for (int i = 0; i < n; ++i) { l[i] = i - 1; while (l[i] >= 0 && a[l[i]] <= a[i]) { l[i] = l[l[i]]; } } Tree dp(n + 1); dp.upd(0, 0); for (int j = 1; j <= k; ++j) { Tree dpp(n + 1); for (int i = 1; i <= n; ++i) { if (l[i - 1] == -1) { dpp.upd(i, dp.get(0, i) + a[i - 1]); } else { dpp.upd(i, min(dpp.get(l[i - 1] + 1, i), dp.get(l[i - 1] + 1, i) + a[i - 1])); } } dp = dpp; } cout << dp.get(n) << "\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...