제출 #413417

#제출 시각아이디문제언어결과실행 시간메모리
413417Tc14The short shank; Redemption (BOI21_prison)C++17
70 / 100
2035 ms28808 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ve vector typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int INF = 1e9 + 10; const ll LLINF = (ll)1e18 + 10; int n, d, t; ve<int> T; struct SegmentTree { int Cap; ve<pll> Seg; ve<ll> L; int left(int x) { return 2 * x; } int right(int x) { return 2 * x + 1; } int parent(int x) { return x / 2; } void build() { Cap = 1 << (int)ceil(log2(n)); Seg = ve<pll>(2 * Cap, {LLINF, -1}); L = ve<ll>(2 * Cap); } void update(int a, int b) { update(a, b, 0, Cap - 1, 1); } void update(int a, int b, int i, int j, int curr) { if (a <= i && j <= b) { Seg[curr].first++; L[curr]++; return; } if (b < i || j < a) return; int m = (i + j) / 2; update(a, b, i, m, left(curr)); update(a, b, m + 1, j, right(curr)); Seg[curr] = min(Seg[left(curr)], Seg[right(curr)]); Seg[curr].first += L[curr]; } void set(int i, pll x) { Seg[Cap + i] = x; int curr = parent(Cap + i); while (curr != 0) { Seg[curr] = min(Seg[left(curr)], Seg[right(curr)]); curr = parent(curr); } } pll getMin() { return Seg[1]; } }; pll calcDP(ll lambda) { stack<int> U; SegmentTree S; S.build(); S.set(n - 1, {0, 0}); if (T[n - 1] > t) U.push(n - 1); else S.update(n - 1, n - 1); for (int i = n - 2; i >= 0; i--) { pll v = S.getMin(); v.first += lambda; v.second++; S.set(i, v); if (T[i] > t) U.push(i); else { int diff = t - T[i]; S.update(i, n - 1); while (U.size() > 0 && (U.top() - i) <= diff) { S.update(U.top(), n - 1); U.pop(); } } } return S.getMin(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> d >> t; T = ve<int>(n); for (int i = 0; i < n; i++) { cin >> T[i]; } ll lo = 0; ll hi = 4e6; ll c, x; while (lo != hi) { ll mi = (lo + hi) / 2; x = calcDP(mi).second; if (x > d) lo = mi + 1; else hi = mi; } tie(c, x) = calcDP(lo); cout << c - d * lo << endl; 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...