Submission #532405

#TimeUsernameProblemLanguageResultExecution timeMemory
5324054fectaThe short shank; Redemption (BOI21_prison)C++17
0 / 100
2092 ms524292 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define int ll #define ld long double #define pii pair<int, int> #define f first #define s second #define boost() cin.tie(0), cin.sync_with_stdio(0) const int MN = 75005; int n, d, T, t[MN]; bitset<MN> b[MN], ones[MN]; vector<vector<int>> dp; void solve(int j, int l, int r, int p1, int p2) { int mid = (l + r) >> 1, opt = 0; for (int i = p1; i <= min(p2, mid); i++) { int len = mid - i + 1; int tmp = (b[i] & (ones[len] << i)).count(); if (dp[mid][j] > dp[i - 1][j - 1] + tmp) { dp[mid][j] = dp[i - 1][j - 1] + tmp; opt = i; } } if (l == r) return; solve(j, l, mid, p1, opt), solve(j, mid + 1, r, opt, p2); } int32_t main() { boost(); cin >> n >> d >> T; vector<vector<int>> tmp(n + 5, vector<int>(d + 5, 0x3f3f3f3f)); dp = tmp; for (int i = 1; i <= n; i++) cin >> t[i]; for (int i = 1; i <= n; i++) ones[i] = ones[i - 1], ones[i][i - 1] = 1; for (int i = n; i > 0; i--) { b[i] = b[i + 1]; if (t[i] > T) continue; int len = min(n - i + 1, T - t[i] + 1); b[i] |= ones[len] << i; } dp[0][0] = 0; for (int i = 1; i <= d + 1; i++) solve(i, 1, n, 1, n); printf("%lld\n", dp[n][d + 1]); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...