Submission #1083524

#TimeUsernameProblemLanguageResultExecution timeMemory
1083524f0rizenK blocks (IZhO14_blocks)C++17
0 / 100
1 ms604 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; } template<typename T, class F = function<T(T, T)>> struct SparseTable { int n; vector<int> lg; vector<vector<T>> st; F func; SparseTable(const vector<T> &a, const F &f) : func(f) { n = a.size(); lg.resize(n + 1); for (int i = 2; i <= n; ++i) { lg[i] = lg[i / 2] + 1; } st.resize(lg[n] + 1, vector<T>(n + 1)); st[0] = a; for (int i = 1; i <= lg[n]; ++i) { for (int j = 0; j + (1 << i) <= n; ++j) { st[i][j] = func(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } } T get(int l, int r) { assert(0 <= l && l < r && r <= n); int i = lg[r - l]; return func(st[i][l], st[i][r - (1 << i)]); } }; 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; SparseTable st(a, [](int a, int b) { return max(a, b); }); auto w = [&](int l, int r) { // [l, r] return st.get(l - 1, r); }; vector<vector<ll>> dp(k + 1, vector<ll>(n + 1, infll)); dp[0][0] = 0; for (int j = 1; j <= k; ++j) { auto solve = [&](auto solve, int l, int r, int optl, int optr) -> void { if (l > r) { return; } int mid = (l + r) / 2; int optm = optl; for (int i = optl; i <= min(optr, mid); ++i) { ll cur = dp[j - 1][i - 1] + w(i, mid); if (dp[j][mid] > cur) { dp[j][mid] = cur; optm = i; } } solve(solve, l, mid - 1, optl, optm); solve(solve, mid + 1, r, optm, optr); }; solve(solve, 1, n, 1, n); } cout << dp[k][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...