Submission #343660

#TimeUsernameProblemLanguageResultExecution timeMemory
343660_aniK blocks (IZhO14_blocks)C++17
53 / 100
1089 ms97644 KiB
#define BUGO(x) cerr << #x << " = " << (x) << '\n'; #include <iostream> #include <algorithm> #include <stack> using namespace std; using ll = long long; const int N = 100'002; const int K = 20; const ll inf = 1'000'000'000'000'000'000LL; ll dp[N][102], a[N]; int lg[N]; ll mn[N][K]; struct el { ll x; int ind; }; bool operator<(const el& a, const el& b) { return a.x < b.x; } void Build(int n, int curk) { int k = lg[n]; for (int i = 0; i < n; i++) mn[i][0] = dp[i + 1][curk]; for (int j = 1; j <= k; j++) for (int i = 0; i + (1 << j) - 1 <= n; i++) mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]); } ll Mn(int l, int r) { l--; r--; int j = lg[r - l + 1]; return min(mn[l][j], mn[r - (1 << j) + 1][j]); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; lg[1] = 0; for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; 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) { 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, i - 1)) + a[i]; } else dp[i][curk] = min(dp[prev.ind][curk], Mn(prev.ind, i - 1) + a[i]); } Build(n, curk); } /*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...