#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Fenwick {
int n;
int tree[2000002];
Fenwick(){}
void init(int _n){
n = _n;
}
void add(int x, int y){
while(x <= n){
tree[x] += y;
x += x&-x;
}
}
int sum(int x){
int ret = 0;
while(x){
ret += tree[x];
x -= x&-x;
}
return ret;
}
int sum(int l, int r){
return sum(r) - sum(l-1);
}
} tree;
struct minSegmentTree{
int tree[8000002], lazy[8000002], maxLoc[8000002];
void init(int i, int l, int r, int* A){
if(l==r){
tree[i] = A[l];
lazy[i] = 0;
maxLoc[i] = l;
return;
}
lazy[i] = 0;
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
if(tree[i*2] >= tree[i*2+1]) tree[i] = tree[i*2], maxLoc[i] = maxLoc[i*2];
else tree[i] = tree[i*2+1], maxLoc[i] = maxLoc[i*2+1];
}
void propagate(int i, int l, int r){
if(!lazy[i]) return;
tree[i] += lazy[i];
if(l!=r) lazy[i*2] += lazy[i], lazy[i*2+1] += lazy[i];
lazy[i] = 0;
}
void update(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, val);
update(i*2+1, m+1, r, s, e, val);
if(tree[i*2] >= tree[i*2+1]) tree[i] = tree[i*2], maxLoc[i] = maxLoc[i*2];
else tree[i] = tree[i*2+1], maxLoc[i] = maxLoc[i*2+1];
}
} mstree;
int n, k, t;
int arr[2000002];
int lLim[2000002];
int basic;
stack<pair<int, int> > stk;
vector<int> link[2000002];
int par[2000002], depth[2000002], sz[2000002];
int vCount, leafCnt;
vector<int> leaf;
int ans;
int DP[4002][4002];
void dfs(int x, int d = 0){
if((int)link[x].size() == 0) depth[x] = d;
else depth[x] = -1e9;
sz[x] = 1;
for(auto y: link[x]){
dfs(y, d+1);
sz[x] += sz[y];
}
}
int tmpArr[2002];
void dfs2(int x){
int currentSize = 1;
for(auto y: link[x]){
dfs2(y);
for(int i=1; i<=currentSize+sz[y] && i<=k; i++) tmpArr[i] = 0;
for(int i=0; i<=currentSize && i<=k; i++){
for(int j=0; j<=sz[y] && i+j<=k; j++){
if(!i && !j) continue;
tmpArr[i+j] = max(tmpArr[i+j], DP[x][i] + DP[y][j]);
}
}
currentSize += sz[y];
for(int i=0; i<=currentSize && i<=k; i++) DP[x][i] = tmpArr[i];
}
for(int i=1; i<=currentSize && i<=k; i++) DP[x][i]++;
}
int main(){
scanf("%d %d %d", &n, &k, &t);
for(int i=1; i<=n; i++){
scanf("%d", &arr[i]);
if(arr[i] <= t) lLim[i] = -1;
else{
while(!stk.empty() && stk.top().first < i) stk.pop();
if(stk.empty()) basic++, lLim[i] = -1;
else lLim[i] = stk.top().second;
}
if(arr[i] < t){
int val = i + (t - arr[i]);
while(!stk.empty() && stk.top().first <= val) stk.pop();
stk.push(make_pair(val, i));
}
}
while(!stk.empty()) stk.pop();
stk.push(make_pair(0, ++vCount));
for(int i=n; i>=1; i--){
if(lLim[i] == -1) continue;
while(stk.top().first > i) stk.pop();
link[stk.top().second].push_back(++vCount);
par[vCount] = stk.top().second;
stk.push(make_pair(lLim[i], vCount));
}
for(int i=1; i<=vCount; i++){
if((int)link[i].size() == 0){
leafCnt++;
leaf.push_back(i);
}
}
dfs(1);
int toCount = min(leafCnt, k);
tree.init(vCount);
mstree.init(1, 1, vCount, depth);
ans = 0;
dfs2(1);
ans = max(0, DP[1][toCount] - 1);
// tree.add(1, 1);
//
// while(toCount--){
// int maxLoc = mstree.maxLoc[1];
// assert(maxLoc != 1);
//
// mstree.update(1, 1, vCount, maxLoc, maxLoc, -1e9);
// while(tree.sum(maxLoc, maxLoc) == 0){
// tree.add(maxLoc, 1);
// mstree.update(1, 1, vCount, maxLoc, maxLoc+sz[maxLoc]-1, 1);
// maxLoc = par[maxLoc];
// ans++;
// }
// }
printf("%d\n", n - (basic + ans));
}
Compilation message
prison.cpp: In function 'int main()':
prison.cpp:119:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d %d %d", &n, &k, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | scanf("%d", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47308 KB |
Output is correct |
2 |
Correct |
29 ms |
48212 KB |
Output is correct |
3 |
Correct |
32 ms |
48036 KB |
Output is correct |
4 |
Correct |
28 ms |
48208 KB |
Output is correct |
5 |
Correct |
33 ms |
48332 KB |
Output is correct |
6 |
Correct |
30 ms |
48696 KB |
Output is correct |
7 |
Correct |
29 ms |
48504 KB |
Output is correct |
8 |
Correct |
28 ms |
48404 KB |
Output is correct |
9 |
Correct |
29 ms |
48460 KB |
Output is correct |
10 |
Correct |
29 ms |
48424 KB |
Output is correct |
11 |
Correct |
29 ms |
48268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47360 KB |
Output is correct |
2 |
Runtime error |
274 ms |
175692 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47308 KB |
Output is correct |
2 |
Correct |
29 ms |
48212 KB |
Output is correct |
3 |
Correct |
32 ms |
48036 KB |
Output is correct |
4 |
Correct |
28 ms |
48208 KB |
Output is correct |
5 |
Correct |
33 ms |
48332 KB |
Output is correct |
6 |
Correct |
30 ms |
48696 KB |
Output is correct |
7 |
Correct |
29 ms |
48504 KB |
Output is correct |
8 |
Correct |
28 ms |
48404 KB |
Output is correct |
9 |
Correct |
29 ms |
48460 KB |
Output is correct |
10 |
Correct |
29 ms |
48424 KB |
Output is correct |
11 |
Correct |
29 ms |
48268 KB |
Output is correct |
12 |
Correct |
27 ms |
47264 KB |
Output is correct |
13 |
Correct |
29 ms |
48192 KB |
Output is correct |
14 |
Correct |
28 ms |
48132 KB |
Output is correct |
15 |
Correct |
29 ms |
48264 KB |
Output is correct |
16 |
Correct |
29 ms |
48372 KB |
Output is correct |
17 |
Correct |
29 ms |
48640 KB |
Output is correct |
18 |
Correct |
28 ms |
48584 KB |
Output is correct |
19 |
Correct |
34 ms |
48292 KB |
Output is correct |
20 |
Correct |
32 ms |
48460 KB |
Output is correct |
21 |
Correct |
31 ms |
48424 KB |
Output is correct |
22 |
Correct |
29 ms |
48232 KB |
Output is correct |
23 |
Correct |
36 ms |
57548 KB |
Output is correct |
24 |
Correct |
39 ms |
55564 KB |
Output is correct |
25 |
Correct |
37 ms |
57636 KB |
Output is correct |
26 |
Correct |
36 ms |
55628 KB |
Output is correct |
27 |
Correct |
37 ms |
57636 KB |
Output is correct |
28 |
Correct |
33 ms |
55744 KB |
Output is correct |
29 |
Correct |
35 ms |
57556 KB |
Output is correct |
30 |
Correct |
32 ms |
54596 KB |
Output is correct |
31 |
Correct |
34 ms |
55620 KB |
Output is correct |
32 |
Correct |
33 ms |
54276 KB |
Output is correct |
33 |
Correct |
32 ms |
54348 KB |
Output is correct |
34 |
Correct |
35 ms |
58240 KB |
Output is correct |
35 |
Correct |
38 ms |
58220 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47308 KB |
Output is correct |
2 |
Runtime error |
177 ms |
148240 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47308 KB |
Output is correct |
2 |
Correct |
29 ms |
48212 KB |
Output is correct |
3 |
Correct |
32 ms |
48036 KB |
Output is correct |
4 |
Correct |
28 ms |
48208 KB |
Output is correct |
5 |
Correct |
33 ms |
48332 KB |
Output is correct |
6 |
Correct |
30 ms |
48696 KB |
Output is correct |
7 |
Correct |
29 ms |
48504 KB |
Output is correct |
8 |
Correct |
28 ms |
48404 KB |
Output is correct |
9 |
Correct |
29 ms |
48460 KB |
Output is correct |
10 |
Correct |
29 ms |
48424 KB |
Output is correct |
11 |
Correct |
29 ms |
48268 KB |
Output is correct |
12 |
Correct |
27 ms |
47264 KB |
Output is correct |
13 |
Correct |
29 ms |
48192 KB |
Output is correct |
14 |
Correct |
28 ms |
48132 KB |
Output is correct |
15 |
Correct |
29 ms |
48264 KB |
Output is correct |
16 |
Correct |
29 ms |
48372 KB |
Output is correct |
17 |
Correct |
29 ms |
48640 KB |
Output is correct |
18 |
Correct |
28 ms |
48584 KB |
Output is correct |
19 |
Correct |
34 ms |
48292 KB |
Output is correct |
20 |
Correct |
32 ms |
48460 KB |
Output is correct |
21 |
Correct |
31 ms |
48424 KB |
Output is correct |
22 |
Correct |
29 ms |
48232 KB |
Output is correct |
23 |
Correct |
36 ms |
57548 KB |
Output is correct |
24 |
Correct |
39 ms |
55564 KB |
Output is correct |
25 |
Correct |
37 ms |
57636 KB |
Output is correct |
26 |
Correct |
36 ms |
55628 KB |
Output is correct |
27 |
Correct |
37 ms |
57636 KB |
Output is correct |
28 |
Correct |
33 ms |
55744 KB |
Output is correct |
29 |
Correct |
35 ms |
57556 KB |
Output is correct |
30 |
Correct |
32 ms |
54596 KB |
Output is correct |
31 |
Correct |
34 ms |
55620 KB |
Output is correct |
32 |
Correct |
33 ms |
54276 KB |
Output is correct |
33 |
Correct |
32 ms |
54348 KB |
Output is correct |
34 |
Correct |
35 ms |
58240 KB |
Output is correct |
35 |
Correct |
38 ms |
58220 KB |
Output is correct |
36 |
Correct |
28 ms |
47308 KB |
Output is correct |
37 |
Runtime error |
177 ms |
148240 KB |
Execution killed with signal 11 |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47308 KB |
Output is correct |
2 |
Correct |
29 ms |
48212 KB |
Output is correct |
3 |
Correct |
32 ms |
48036 KB |
Output is correct |
4 |
Correct |
28 ms |
48208 KB |
Output is correct |
5 |
Correct |
33 ms |
48332 KB |
Output is correct |
6 |
Correct |
30 ms |
48696 KB |
Output is correct |
7 |
Correct |
29 ms |
48504 KB |
Output is correct |
8 |
Correct |
28 ms |
48404 KB |
Output is correct |
9 |
Correct |
29 ms |
48460 KB |
Output is correct |
10 |
Correct |
29 ms |
48424 KB |
Output is correct |
11 |
Correct |
29 ms |
48268 KB |
Output is correct |
12 |
Correct |
28 ms |
47360 KB |
Output is correct |
13 |
Runtime error |
274 ms |
175692 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |