Submission #523674

#TimeUsernameProblemLanguageResultExecution timeMemory
523674boykutK blocks (IZhO14_blocks)C++14
53 / 100
1081 ms3276 KiB
#include <bits/stdc++.h> using namespace std; class sparse_table { public: sparse_table(vector<int>&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<int>(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]); } int 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<int>> mx; }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(1 + n); for (int i = 1; i <= n; i++) { cin >> a[i]; } sparse_table st(a); vector<vector<long long>> dp(1 + k, vector<long long>(1 + n, 1e18)); for (int i = 1; i <= n; i++) { dp[1][i] = st.query(1, i); } for (int j = 2; j <= k; j++) { for (int i = 1; i <= n; i++) { long long mn = 1e18; for (int i2 = 1; i2 < i; i2++) { mn = min(mn, dp[j-1][i2] + st.query(i2+1, i)); } dp[j][i] = mn; } } 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...