# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
411483 | 2021-05-25T11:55:44 Z | 송준혁(#7512) | The short shank; Redemption (BOI21_prison) | C++17 | 177 ms | 10208 KB |
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define lb lower_bound #define MOD 1000000007 #define INF (1ll<<62) using namespace std; typedef long long LL; typedef pair<int,int> pii; int N, M, K, T, ans; int C[2020202]; LL D[2020202]; pii A[2020202]; vector<pii> S; int main(){ int a; scanf("%d %d %d", &N, &K, &T); for (int i=1; i<=N; i++){ scanf("%d", &a); if (T<a){ while (S.size() && S.back().fi < i) S.pop_back(); if (S.size()) A[++M] = pii(S.back().se, i-1); } else S.pb(pii(i+T-a, i)); } int lo=0, hi=N; while (lo<=hi){ int m=lo+hi>>1; int l=1, r=0; for (int i=1; i<=N; i++){ while (l <= M && A[l].se < i) l++; while (r < M && A[r+1].fi <= i) r++; D[i] = D[i-1], C[i] = C[i-1]; if (l<=r){ if (D[A[l].fi-1]+r-l+1-m > D[i] || (D[A[l].fi-1]+r-l+1-m == D[i] && C[A[l].fi-1]+1 < C[i])){ D[i] = D[A[l].fi-1]+r-l+1-m; C[i] = C[A[l].fi-1]+1; } } } if (C[N] <= K) ans = D[N] + (LL)m*K, hi=m-1; else lo=m+1; } printf("%d\n", N-ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Incorrect | 1 ms | 204 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Incorrect | 177 ms | 10208 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Incorrect | 1 ms | 204 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Incorrect | 26 ms | 1860 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Incorrect | 1 ms | 204 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | Output is correct |
2 | Correct | 1 ms | 204 KB | Output is correct |
3 | Correct | 1 ms | 204 KB | Output is correct |
4 | Correct | 1 ms | 204 KB | Output is correct |
5 | Incorrect | 1 ms | 204 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |