# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
399260 | 2021-05-05T13:40:34 Z | LucaDantas | The short shank; Redemption (BOI21_prison) | C++17 | 670 ms | 141236 KB |
#include <bits/stdc++.h> using namespace std; constexpr int maxn = 2e6+10; vector<int> g[maxn]; int a[maxn], add[maxn], rmv[maxn], dp[maxn], ans; vector<int> roots, b, st; vector<int> bfs() { queue<int> q; vector<int> ord; for(int x : roots) q.push(x); while(q.size()) { int u = q.front(); q.pop(); ord.push_back(u); for(int v : g[u]) q.push(v); } reverse(ord.begin(), ord.end()); return ord; } int main() { int n, d, t; scanf("%d %d %d", &n, &d, &t); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); if(a[i] <= t) add[i] = min(n, i + t - a[i]), ++rmv[min(n, i + t - a[i]) + 1], ++ans; } for(int i = 1, atv = 0; i <= n; i++) { atv -= rmv[i]; if(add[i]) { ++atv; st.push_back(add[i] + n); } else { if(!atv) continue; ++ans; while(st.size()) { if(st.back() > n && st.back()-n >= i) break; if(st.back() <= n) g[i].push_back(st.back()); st.pop_back(); } st.push_back(i); } } while(st.size()) { if(st.back() <= n) roots.push_back(st.back()); st.pop_back(); } vector<int> ord = bfs(); for(int u : ord) { if(!g[u].size()) dp[u] = 1; else { vector<int> here; int mx = 0, ok = 0; for(int v : g[u]) here.push_back(dp[v]), mx = max(mx, here.back()); for(int x : here) if(x == mx && !ok) ok = 1; else b.push_back(x); dp[u] = mx+1; } } for(int x : roots) b.push_back(dp[x]); sort(b.begin(), b.end()); while(d-- && b.size()) ans -= b.back(), b.pop_back(); printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 47180 KB | Output is correct |
2 | Correct | 30 ms | 47308 KB | Output is correct |
3 | Correct | 31 ms | 47308 KB | Output is correct |
4 | Correct | 30 ms | 47240 KB | Output is correct |
5 | Correct | 29 ms | 47300 KB | Output is correct |
6 | Correct | 30 ms | 47436 KB | Output is correct |
7 | Correct | 29 ms | 47212 KB | Output is correct |
8 | Correct | 30 ms | 47252 KB | Output is correct |
9 | Correct | 32 ms | 47308 KB | Output is correct |
10 | Correct | 29 ms | 47232 KB | Output is correct |
11 | Correct | 28 ms | 47248 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 47244 KB | Output is correct |
2 | Correct | 151 ms | 68372 KB | Output is correct |
3 | Correct | 126 ms | 64576 KB | Output is correct |
4 | Correct | 138 ms | 65556 KB | Output is correct |
5 | Correct | 190 ms | 67496 KB | Output is correct |
6 | Correct | 124 ms | 63808 KB | Output is correct |
7 | Correct | 146 ms | 73396 KB | Output is correct |
8 | Correct | 134 ms | 66404 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 47180 KB | Output is correct |
2 | Correct | 30 ms | 47308 KB | Output is correct |
3 | Correct | 31 ms | 47308 KB | Output is correct |
4 | Correct | 30 ms | 47240 KB | Output is correct |
5 | Correct | 29 ms | 47300 KB | Output is correct |
6 | Correct | 30 ms | 47436 KB | Output is correct |
7 | Correct | 29 ms | 47212 KB | Output is correct |
8 | Correct | 30 ms | 47252 KB | Output is correct |
9 | Correct | 32 ms | 47308 KB | Output is correct |
10 | Correct | 29 ms | 47232 KB | Output is correct |
11 | Correct | 28 ms | 47248 KB | Output is correct |
12 | Correct | 31 ms | 47276 KB | Output is correct |
13 | Correct | 30 ms | 47308 KB | Output is correct |
14 | Correct | 30 ms | 47236 KB | Output is correct |
15 | Correct | 30 ms | 47276 KB | Output is correct |
16 | Correct | 31 ms | 47300 KB | Output is correct |
17 | Correct | 31 ms | 47272 KB | Output is correct |
18 | Correct | 30 ms | 47284 KB | Output is correct |
19 | Correct | 29 ms | 47232 KB | Output is correct |
20 | Correct | 29 ms | 47300 KB | Output is correct |
21 | Correct | 30 ms | 47208 KB | Output is correct |
22 | Correct | 31 ms | 47308 KB | Output is correct |
23 | Correct | 31 ms | 47404 KB | Output is correct |
24 | Correct | 33 ms | 47436 KB | Output is correct |
25 | Correct | 31 ms | 47412 KB | Output is correct |
26 | Correct | 30 ms | 47436 KB | Output is correct |
27 | Correct | 31 ms | 47428 KB | Output is correct |
28 | Correct | 31 ms | 47436 KB | Output is correct |
29 | Correct | 31 ms | 47340 KB | Output is correct |
30 | Correct | 32 ms | 47344 KB | Output is correct |
31 | Correct | 30 ms | 47352 KB | Output is correct |
32 | Correct | 30 ms | 47440 KB | Output is correct |
33 | Correct | 30 ms | 47436 KB | Output is correct |
34 | Correct | 31 ms | 47436 KB | Output is correct |
35 | Correct | 31 ms | 47428 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 31 ms | 47264 KB | Output is correct |
2 | Correct | 47 ms | 50452 KB | Output is correct |
3 | Correct | 46 ms | 50396 KB | Output is correct |
4 | Correct | 46 ms | 50260 KB | Output is correct |
5 | Correct | 47 ms | 50780 KB | Output is correct |
6 | Correct | 47 ms | 50932 KB | Output is correct |
7 | Correct | 43 ms | 49676 KB | Output is correct |
8 | Correct | 45 ms | 49476 KB | Output is correct |
9 | Correct | 48 ms | 51140 KB | Output is correct |
10 | Correct | 42 ms | 50012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 47180 KB | Output is correct |
2 | Correct | 30 ms | 47308 KB | Output is correct |
3 | Correct | 31 ms | 47308 KB | Output is correct |
4 | Correct | 30 ms | 47240 KB | Output is correct |
5 | Correct | 29 ms | 47300 KB | Output is correct |
6 | Correct | 30 ms | 47436 KB | Output is correct |
7 | Correct | 29 ms | 47212 KB | Output is correct |
8 | Correct | 30 ms | 47252 KB | Output is correct |
9 | Correct | 32 ms | 47308 KB | Output is correct |
10 | Correct | 29 ms | 47232 KB | Output is correct |
11 | Correct | 28 ms | 47248 KB | Output is correct |
12 | Correct | 31 ms | 47276 KB | Output is correct |
13 | Correct | 30 ms | 47308 KB | Output is correct |
14 | Correct | 30 ms | 47236 KB | Output is correct |
15 | Correct | 30 ms | 47276 KB | Output is correct |
16 | Correct | 31 ms | 47300 KB | Output is correct |
17 | Correct | 31 ms | 47272 KB | Output is correct |
18 | Correct | 30 ms | 47284 KB | Output is correct |
19 | Correct | 29 ms | 47232 KB | Output is correct |
20 | Correct | 29 ms | 47300 KB | Output is correct |
21 | Correct | 30 ms | 47208 KB | Output is correct |
22 | Correct | 31 ms | 47308 KB | Output is correct |
23 | Correct | 31 ms | 47404 KB | Output is correct |
24 | Correct | 33 ms | 47436 KB | Output is correct |
25 | Correct | 31 ms | 47412 KB | Output is correct |
26 | Correct | 30 ms | 47436 KB | Output is correct |
27 | Correct | 31 ms | 47428 KB | Output is correct |
28 | Correct | 31 ms | 47436 KB | Output is correct |
29 | Correct | 31 ms | 47340 KB | Output is correct |
30 | Correct | 32 ms | 47344 KB | Output is correct |
31 | Correct | 30 ms | 47352 KB | Output is correct |
32 | Correct | 30 ms | 47440 KB | Output is correct |
33 | Correct | 30 ms | 47436 KB | Output is correct |
34 | Correct | 31 ms | 47436 KB | Output is correct |
35 | Correct | 31 ms | 47428 KB | Output is correct |
36 | Correct | 31 ms | 47264 KB | Output is correct |
37 | Correct | 47 ms | 50452 KB | Output is correct |
38 | Correct | 46 ms | 50396 KB | Output is correct |
39 | Correct | 46 ms | 50260 KB | Output is correct |
40 | Correct | 47 ms | 50780 KB | Output is correct |
41 | Correct | 47 ms | 50932 KB | Output is correct |
42 | Correct | 43 ms | 49676 KB | Output is correct |
43 | Correct | 45 ms | 49476 KB | Output is correct |
44 | Correct | 48 ms | 51140 KB | Output is correct |
45 | Correct | 42 ms | 50012 KB | Output is correct |
46 | Correct | 31 ms | 47296 KB | Output is correct |
47 | Correct | 32 ms | 47288 KB | Output is correct |
48 | Correct | 31 ms | 47272 KB | Output is correct |
49 | Correct | 29 ms | 47312 KB | Output is correct |
50 | Correct | 30 ms | 47304 KB | Output is correct |
51 | Correct | 30 ms | 47300 KB | Output is correct |
52 | Correct | 31 ms | 47372 KB | Output is correct |
53 | Correct | 31 ms | 47256 KB | Output is correct |
54 | Correct | 30 ms | 47308 KB | Output is correct |
55 | Correct | 30 ms | 47308 KB | Output is correct |
56 | Correct | 30 ms | 47272 KB | Output is correct |
57 | Correct | 31 ms | 47484 KB | Output is correct |
58 | Correct | 30 ms | 47364 KB | Output is correct |
59 | Correct | 31 ms | 47428 KB | Output is correct |
60 | Correct | 29 ms | 47388 KB | Output is correct |
61 | Correct | 31 ms | 47364 KB | Output is correct |
62 | Correct | 31 ms | 47416 KB | Output is correct |
63 | Correct | 30 ms | 47484 KB | Output is correct |
64 | Correct | 30 ms | 47436 KB | Output is correct |
65 | Correct | 31 ms | 47460 KB | Output is correct |
66 | Correct | 32 ms | 47368 KB | Output is correct |
67 | Correct | 31 ms | 47380 KB | Output is correct |
68 | Correct | 32 ms | 47400 KB | Output is correct |
69 | Correct | 30 ms | 47408 KB | Output is correct |
70 | Correct | 30 ms | 47308 KB | Output is correct |
71 | Correct | 47 ms | 50420 KB | Output is correct |
72 | Correct | 45 ms | 50432 KB | Output is correct |
73 | Correct | 46 ms | 50288 KB | Output is correct |
74 | Correct | 46 ms | 50884 KB | Output is correct |
75 | Correct | 54 ms | 50880 KB | Output is correct |
76 | Correct | 42 ms | 49604 KB | Output is correct |
77 | Correct | 43 ms | 49468 KB | Output is correct |
78 | Correct | 48 ms | 51152 KB | Output is correct |
79 | Correct | 43 ms | 49984 KB | Output is correct |
80 | Correct | 48 ms | 50396 KB | Output is correct |
81 | Correct | 47 ms | 50460 KB | Output is correct |
82 | Correct | 46 ms | 50400 KB | Output is correct |
83 | Correct | 46 ms | 50368 KB | Output is correct |
84 | Correct | 45 ms | 50120 KB | Output is correct |
85 | Correct | 47 ms | 51236 KB | Output is correct |
86 | Correct | 47 ms | 50240 KB | Output is correct |
87 | Correct | 44 ms | 49612 KB | Output is correct |
88 | Correct | 46 ms | 50792 KB | Output is correct |
89 | Correct | 47 ms | 51108 KB | Output is correct |
90 | Correct | 51 ms | 50584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 47180 KB | Output is correct |
2 | Correct | 30 ms | 47308 KB | Output is correct |
3 | Correct | 31 ms | 47308 KB | Output is correct |
4 | Correct | 30 ms | 47240 KB | Output is correct |
5 | Correct | 29 ms | 47300 KB | Output is correct |
6 | Correct | 30 ms | 47436 KB | Output is correct |
7 | Correct | 29 ms | 47212 KB | Output is correct |
8 | Correct | 30 ms | 47252 KB | Output is correct |
9 | Correct | 32 ms | 47308 KB | Output is correct |
10 | Correct | 29 ms | 47232 KB | Output is correct |
11 | Correct | 28 ms | 47248 KB | Output is correct |
12 | Correct | 30 ms | 47244 KB | Output is correct |
13 | Correct | 151 ms | 68372 KB | Output is correct |
14 | Correct | 126 ms | 64576 KB | Output is correct |
15 | Correct | 138 ms | 65556 KB | Output is correct |
16 | Correct | 190 ms | 67496 KB | Output is correct |
17 | Correct | 124 ms | 63808 KB | Output is correct |
18 | Correct | 146 ms | 73396 KB | Output is correct |
19 | Correct | 134 ms | 66404 KB | Output is correct |
20 | Correct | 31 ms | 47276 KB | Output is correct |
21 | Correct | 30 ms | 47308 KB | Output is correct |
22 | Correct | 30 ms | 47236 KB | Output is correct |
23 | Correct | 30 ms | 47276 KB | Output is correct |
24 | Correct | 31 ms | 47300 KB | Output is correct |
25 | Correct | 31 ms | 47272 KB | Output is correct |
26 | Correct | 30 ms | 47284 KB | Output is correct |
27 | Correct | 29 ms | 47232 KB | Output is correct |
28 | Correct | 29 ms | 47300 KB | Output is correct |
29 | Correct | 30 ms | 47208 KB | Output is correct |
30 | Correct | 31 ms | 47308 KB | Output is correct |
31 | Correct | 31 ms | 47404 KB | Output is correct |
32 | Correct | 33 ms | 47436 KB | Output is correct |
33 | Correct | 31 ms | 47412 KB | Output is correct |
34 | Correct | 30 ms | 47436 KB | Output is correct |
35 | Correct | 31 ms | 47428 KB | Output is correct |
36 | Correct | 31 ms | 47436 KB | Output is correct |
37 | Correct | 31 ms | 47340 KB | Output is correct |
38 | Correct | 32 ms | 47344 KB | Output is correct |
39 | Correct | 30 ms | 47352 KB | Output is correct |
40 | Correct | 30 ms | 47440 KB | Output is correct |
41 | Correct | 30 ms | 47436 KB | Output is correct |
42 | Correct | 31 ms | 47436 KB | Output is correct |
43 | Correct | 31 ms | 47428 KB | Output is correct |
44 | Correct | 31 ms | 47264 KB | Output is correct |
45 | Correct | 47 ms | 50452 KB | Output is correct |
46 | Correct | 46 ms | 50396 KB | Output is correct |
47 | Correct | 46 ms | 50260 KB | Output is correct |
48 | Correct | 47 ms | 50780 KB | Output is correct |
49 | Correct | 47 ms | 50932 KB | Output is correct |
50 | Correct | 43 ms | 49676 KB | Output is correct |
51 | Correct | 45 ms | 49476 KB | Output is correct |
52 | Correct | 48 ms | 51140 KB | Output is correct |
53 | Correct | 42 ms | 50012 KB | Output is correct |
54 | Correct | 31 ms | 47296 KB | Output is correct |
55 | Correct | 32 ms | 47288 KB | Output is correct |
56 | Correct | 31 ms | 47272 KB | Output is correct |
57 | Correct | 29 ms | 47312 KB | Output is correct |
58 | Correct | 30 ms | 47304 KB | Output is correct |
59 | Correct | 30 ms | 47300 KB | Output is correct |
60 | Correct | 31 ms | 47372 KB | Output is correct |
61 | Correct | 31 ms | 47256 KB | Output is correct |
62 | Correct | 30 ms | 47308 KB | Output is correct |
63 | Correct | 30 ms | 47308 KB | Output is correct |
64 | Correct | 30 ms | 47272 KB | Output is correct |
65 | Correct | 31 ms | 47484 KB | Output is correct |
66 | Correct | 30 ms | 47364 KB | Output is correct |
67 | Correct | 31 ms | 47428 KB | Output is correct |
68 | Correct | 29 ms | 47388 KB | Output is correct |
69 | Correct | 31 ms | 47364 KB | Output is correct |
70 | Correct | 31 ms | 47416 KB | Output is correct |
71 | Correct | 30 ms | 47484 KB | Output is correct |
72 | Correct | 30 ms | 47436 KB | Output is correct |
73 | Correct | 31 ms | 47460 KB | Output is correct |
74 | Correct | 32 ms | 47368 KB | Output is correct |
75 | Correct | 31 ms | 47380 KB | Output is correct |
76 | Correct | 32 ms | 47400 KB | Output is correct |
77 | Correct | 30 ms | 47408 KB | Output is correct |
78 | Correct | 30 ms | 47308 KB | Output is correct |
79 | Correct | 47 ms | 50420 KB | Output is correct |
80 | Correct | 45 ms | 50432 KB | Output is correct |
81 | Correct | 46 ms | 50288 KB | Output is correct |
82 | Correct | 46 ms | 50884 KB | Output is correct |
83 | Correct | 54 ms | 50880 KB | Output is correct |
84 | Correct | 42 ms | 49604 KB | Output is correct |
85 | Correct | 43 ms | 49468 KB | Output is correct |
86 | Correct | 48 ms | 51152 KB | Output is correct |
87 | Correct | 43 ms | 49984 KB | Output is correct |
88 | Correct | 48 ms | 50396 KB | Output is correct |
89 | Correct | 47 ms | 50460 KB | Output is correct |
90 | Correct | 46 ms | 50400 KB | Output is correct |
91 | Correct | 46 ms | 50368 KB | Output is correct |
92 | Correct | 45 ms | 50120 KB | Output is correct |
93 | Correct | 47 ms | 51236 KB | Output is correct |
94 | Correct | 47 ms | 50240 KB | Output is correct |
95 | Correct | 44 ms | 49612 KB | Output is correct |
96 | Correct | 46 ms | 50792 KB | Output is correct |
97 | Correct | 47 ms | 51108 KB | Output is correct |
98 | Correct | 51 ms | 50584 KB | Output is correct |
99 | Correct | 31 ms | 47288 KB | Output is correct |
100 | Correct | 30 ms | 47300 KB | Output is correct |
101 | Correct | 30 ms | 47264 KB | Output is correct |
102 | Correct | 29 ms | 47264 KB | Output is correct |
103 | Correct | 30 ms | 47308 KB | Output is correct |
104 | Correct | 30 ms | 47308 KB | Output is correct |
105 | Correct | 29 ms | 47300 KB | Output is correct |
106 | Correct | 30 ms | 47328 KB | Output is correct |
107 | Correct | 34 ms | 47252 KB | Output is correct |
108 | Correct | 34 ms | 47252 KB | Output is correct |
109 | Correct | 30 ms | 47300 KB | Output is correct |
110 | Correct | 30 ms | 47180 KB | Output is correct |
111 | Correct | 150 ms | 68364 KB | Output is correct |
112 | Correct | 127 ms | 64548 KB | Output is correct |
113 | Correct | 134 ms | 65616 KB | Output is correct |
114 | Correct | 167 ms | 67548 KB | Output is correct |
115 | Correct | 125 ms | 63792 KB | Output is correct |
116 | Correct | 145 ms | 73436 KB | Output is correct |
117 | Correct | 131 ms | 66500 KB | Output is correct |
118 | Correct | 31 ms | 47444 KB | Output is correct |
119 | Correct | 31 ms | 47384 KB | Output is correct |
120 | Correct | 32 ms | 47416 KB | Output is correct |
121 | Correct | 30 ms | 47480 KB | Output is correct |
122 | Correct | 30 ms | 47428 KB | Output is correct |
123 | Correct | 32 ms | 47376 KB | Output is correct |
124 | Correct | 31 ms | 47424 KB | Output is correct |
125 | Correct | 31 ms | 47432 KB | Output is correct |
126 | Correct | 30 ms | 47436 KB | Output is correct |
127 | Correct | 31 ms | 47356 KB | Output is correct |
128 | Correct | 31 ms | 47420 KB | Output is correct |
129 | Correct | 29 ms | 47440 KB | Output is correct |
130 | Correct | 31 ms | 47428 KB | Output is correct |
131 | Correct | 30 ms | 47212 KB | Output is correct |
132 | Correct | 47 ms | 50476 KB | Output is correct |
133 | Correct | 47 ms | 50396 KB | Output is correct |
134 | Correct | 46 ms | 50288 KB | Output is correct |
135 | Correct | 46 ms | 50760 KB | Output is correct |
136 | Correct | 46 ms | 50880 KB | Output is correct |
137 | Correct | 44 ms | 49616 KB | Output is correct |
138 | Correct | 45 ms | 49428 KB | Output is correct |
139 | Correct | 47 ms | 51140 KB | Output is correct |
140 | Correct | 43 ms | 49964 KB | Output is correct |
141 | Correct | 46 ms | 50412 KB | Output is correct |
142 | Correct | 47 ms | 50400 KB | Output is correct |
143 | Correct | 46 ms | 50408 KB | Output is correct |
144 | Correct | 46 ms | 50368 KB | Output is correct |
145 | Correct | 47 ms | 50264 KB | Output is correct |
146 | Correct | 48 ms | 51124 KB | Output is correct |
147 | Correct | 46 ms | 50200 KB | Output is correct |
148 | Correct | 43 ms | 49604 KB | Output is correct |
149 | Correct | 46 ms | 50752 KB | Output is correct |
150 | Correct | 47 ms | 51068 KB | Output is correct |
151 | Correct | 45 ms | 50588 KB | Output is correct |
152 | Correct | 523 ms | 131676 KB | Output is correct |
153 | Correct | 517 ms | 130020 KB | Output is correct |
154 | Correct | 475 ms | 125852 KB | Output is correct |
155 | Correct | 485 ms | 129952 KB | Output is correct |
156 | Correct | 670 ms | 128288 KB | Output is correct |
157 | Correct | 403 ms | 106152 KB | Output is correct |
158 | Correct | 444 ms | 119632 KB | Output is correct |
159 | Correct | 489 ms | 141236 KB | Output is correct |
160 | Correct | 516 ms | 136132 KB | Output is correct |
161 | Correct | 388 ms | 110256 KB | Output is correct |
162 | Correct | 408 ms | 109896 KB | Output is correct |