Submission #523766

#TimeUsernameProblemLanguageResultExecution timeMemory
523766boykutK blocks (IZhO14_blocks)C++14
0 / 100
1 ms236 KiB
#include <bits/stdc++.h> using namespace std; class segment_tree { public: segment_tree(size_t s) { n = 1; while (n < s) n <<= 1; t.assign(2 * n, 1e18); } void build(vector<long long> & a, int v, int vl, int vr) { if (vl == vr) { t[v] = a[vl]; } else { int vm = (vl + vr) >> 1; build(a, v << 1, vl, vm); build(a, v << 1 | 1, vm + 1, vr); t[v] = min(t[v << 1], t[v << 1 | 1]); } } void build(vector<long long> & a) { build(a, 1, 0, n - 1); } void update(int i, long long x, int v, int vl, int vr) { if (vl == vr) { t[v] = x; } else { int vm = (vl + vr) >> 1; if (i <= vm) update(i, x, v << 1, vl, vm); else update(i, x, v << 1 | 1, vm + 1, vr); t[v] = min(t[v << 1], t[v << 1 | 1]); } } void update(int i, long long x) { update(i, x, 1, 0, n - 1); } long long query(int l, int r, int v, int vl, int vr) { if (l > vr || vl > r) return 1e18; if (l <= vl && vr <= r) return t[v]; int vm = (vl + vr) >> 1; auto q1 = query(l, r, v << 1, vl, vm); auto q2 = query(l, r, v << 1 | 1, vm + 1, vr); return min(q1, q2); } long long query(int l, int r) { return query(l, r, 1, 0, n - 1); } private: int n; vector<long long> t; }; class sparse_table_max { public: sparse_table_max(vector<long long>&a) : n(a.size()) { lg.resize(1 + n); lg[0] = lg[1] = 0; for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; mx.assign(n, vector<long long>(1 + lg[n])); for (int j = 0; j <= lg[n]; j++) for (int i = 0; i <= n - (1 << j); i++) if (j == 0) mx[i][j] = a[i]; else mx[i][j] = max(mx[i][j-1], mx[i+(1<<(j-1))][j-1]); } long long query(int l, int r) { int d = lg[r-l+1]; return max(mx[l][d], mx[r-(1<<d)+1][d]); } private: int n; vector<int> lg; vector<vector<long long>> mx; }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; vector<long long> a(1 + n); for (int i = 1; i <= n; i++) { cin >> a[i]; } sparse_table_max st(a); segment_tree str(n + 1); vector<vector<long long>> dp(1 + n, vector<long long>(1 + k, 1e18)); //a[0] = 1e18; for (int i = 1; i <= n; i++) { dp[i][1] = st.query(1, i); a[i] = dp[i][1]; str.update(i, a[i]); } //str.build(a); vector<int> left(n + 1, 0); for (int i = 2; i <= n; i++) { int l = 1, r = i; while (l < r) { int m = (l + r) / 2; if (st.query(m, i) == a[i]) r = m; else l = m + 1; } left[i] = r; } int K = k; for (int k = 2; k <= K; k++) { for (int i = 2; i <= n; i++) { int r = left[i]; dp[i][k] = min(dp[i][k], dp[r - 1][k]); if (st.query(r, i) == a[i]) { long long mn = str.query(r - 1, i - 1); dp[i][k] = min(dp[i][k], mn + a[i]); } } for (int i = 0; i <= n; i++) { a[i] = dp[i][k]; } str.build(a); } cout << dp[n][k] << '\n'; return 0; }

Compilation message (stderr)

blocks.cpp: In constructor 'segment_tree::segment_tree(size_t)':
blocks.cpp:9:12: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
    9 |   while (n < s) n <<= 1;
      |          ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...