| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 444323 | 8e7 | The short shank; Redemption (BOI21_prison) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b ...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 2000005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
int rig[maxn], dep[maxn], ma[maxn];
vector<int> adj[maxn], val;
stack<int> stk, tree;
void dfs(int n, int par, int d) {
dep[n] = d;
for (int v:adj[n]) dfs(v, n, d + 1), dep[n] = max(dep[n], dep[v]);
}
void dfs2(int n, int par, int to, int d) {
ma[to] = max(ma[to], dep[to] - d + 1);
int best = 0, bind = 0;
for (int v:adj[n]) {
if (dep[v] > best) best = dep[v], bind = v;
}
for (int v:adj[n]) {
if (v == bind) dfs2(v, n, to);
else dfs2(v, n, v);
}
}
int main() {
io
int n, k, t;
cin >> n >> k >> t;
for (int i = 1;i <= n;i++) {
int ti;
cin >> ti;
if (ti <= t) {
rig[i] = min(n, i + t - ti); //[i, a[i]]
}
}
int cnt = 0;
for (int i = n;i > 0;i--) {
if (rig[i]) {
cnt++;
while (stk.size() && rig[i] >= stk.top()) {
int cur = stk.top();stk.pop();
cnt++;
while (tree.size() && cur > tree.top()) {
adj[cur].push_back(tree.top());
tree.pop();
}
tree.push(cur);
}
} else {
stk.push(i);
}
}
while (tree.size()) {
adj[0].push_back(tree.top()), tree.pop();
}
dfs(0, 0, 0);
dfs2(0, 0, 0);
for (int i = 0;i <= n;i++) {
if (ma[i]) val.push_back(ma[i]);
}
sort(val.begin(), val.end(), [&] (int x, int y) {return x > y;});
for (int i = 0;i < min(k, int(val.size()));i++) cnt -= val[i];
cout << cnt + 1 << endl;
}
/*
5 1 42
13 37 47 11 42
5 2 5
1 9 4 6 7
6 2 6
1 3 5 8 9 10
*/