# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
952798 | 2024-03-24T20:40:49 Z | stakaman | Swimming competition (LMIO18_plaukimo_varzybos) | C++17 | 360 ms | 16212 KB |
#include <bits/stdc++.h> using namespace std; const int N = 1000006; int n, a, b; int u[N]; int p[N]; bool dp[N]; bool solve(int x){ dp[0] = true; p[0] = 1; int j = 1; for (int i = 1; i <= n; ++i) { p[i] = p[i - 1]; dp[i] = false; while ((u[i] - u[j] > x)) ++j; if (i - a < 0) continue; if (j - 1 <= i - b) { if (i - b - 1 < 0) dp[i] = true; else if (p[i - a] - p[i - b - 1] > 0) dp[i] = true; } else { if (j - 1 <= i - a) { if (p[i - a] - p[j - 1 - 1] > 0) dp[i] = true; } } if (dp[i]) ++p[i]; } return dp[n]; } int main(){ scanf("%d%d%d", &n, &a, &b); for (int i = 1; i <= n; ++i) scanf("%d", &u[i]); sort(u + 1, u + n + 1); int l = 0, r = N; int ans; while (l <= r) { int m = (l + r) / 2; if (solve(m)){ ans = m; r = m - 1; } else l = m + 1; } printf("%d\n", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4536 KB | Output is correct |
2 | Correct | 17 ms | 5320 KB | Output is correct |
3 | Correct | 4 ms | 4444 KB | Output is correct |
4 | Correct | 359 ms | 15776 KB | Output is correct |
5 | Correct | 354 ms | 16148 KB | Output is correct |
6 | Correct | 19 ms | 5208 KB | Output is correct |
7 | Correct | 318 ms | 14888 KB | Output is correct |
8 | Correct | 1 ms | 4444 KB | Output is correct |
9 | Correct | 1 ms | 4444 KB | Output is correct |
10 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4444 KB | Output is correct |
2 | Correct | 1 ms | 4444 KB | Output is correct |
3 | Correct | 1 ms | 4444 KB | Output is correct |
4 | Correct | 1 ms | 4440 KB | Output is correct |
5 | Correct | 1 ms | 4444 KB | Output is correct |
6 | Correct | 1 ms | 4444 KB | Output is correct |
7 | Correct | 1 ms | 4444 KB | Output is correct |
8 | Correct | 2 ms | 4444 KB | Output is correct |
9 | Correct | 1 ms | 4444 KB | Output is correct |
10 | Correct | 1 ms | 4444 KB | Output is correct |
11 | Correct | 1 ms | 4444 KB | Output is correct |
12 | Correct | 1 ms | 4444 KB | Output is correct |
13 | Correct | 1 ms | 4444 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4536 KB | Output is correct |
2 | Correct | 17 ms | 5320 KB | Output is correct |
3 | Correct | 4 ms | 4444 KB | Output is correct |
4 | Correct | 359 ms | 15776 KB | Output is correct |
5 | Correct | 354 ms | 16148 KB | Output is correct |
6 | Correct | 19 ms | 5208 KB | Output is correct |
7 | Correct | 318 ms | 14888 KB | Output is correct |
8 | Correct | 1 ms | 4444 KB | Output is correct |
9 | Correct | 1 ms | 4444 KB | Output is correct |
10 | Correct | 1 ms | 4444 KB | Output is correct |
11 | Correct | 1 ms | 4440 KB | Output is correct |
12 | Correct | 1 ms | 4444 KB | Output is correct |
13 | Correct | 1 ms | 4444 KB | Output is correct |
14 | Correct | 1 ms | 4444 KB | Output is correct |
15 | Correct | 2 ms | 4444 KB | Output is correct |
16 | Correct | 1 ms | 4444 KB | Output is correct |
17 | Correct | 1 ms | 4444 KB | Output is correct |
18 | Correct | 1 ms | 4444 KB | Output is correct |
19 | Correct | 1 ms | 4444 KB | Output is correct |
20 | Correct | 1 ms | 4444 KB | Output is correct |
21 | Correct | 7 ms | 4700 KB | Output is correct |
22 | Correct | 7 ms | 4688 KB | Output is correct |
23 | Correct | 12 ms | 4784 KB | Output is correct |
24 | Correct | 28 ms | 5080 KB | Output is correct |
25 | Correct | 99 ms | 10680 KB | Output is correct |
26 | Correct | 288 ms | 14164 KB | Output is correct |
27 | Correct | 26 ms | 5080 KB | Output is correct |
28 | Correct | 12 ms | 4696 KB | Output is correct |
29 | Correct | 1 ms | 4444 KB | Output is correct |
30 | Correct | 336 ms | 16088 KB | Output is correct |
31 | Correct | 342 ms | 15776 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 4536 KB | Output is correct |
2 | Correct | 17 ms | 5320 KB | Output is correct |
3 | Correct | 4 ms | 4444 KB | Output is correct |
4 | Correct | 359 ms | 15776 KB | Output is correct |
5 | Correct | 354 ms | 16148 KB | Output is correct |
6 | Correct | 19 ms | 5208 KB | Output is correct |
7 | Correct | 318 ms | 14888 KB | Output is correct |
8 | Correct | 1 ms | 4444 KB | Output is correct |
9 | Correct | 1 ms | 4444 KB | Output is correct |
10 | Correct | 1 ms | 4444 KB | Output is correct |
11 | Correct | 7 ms | 4700 KB | Output is correct |
12 | Correct | 7 ms | 4688 KB | Output is correct |
13 | Correct | 12 ms | 4784 KB | Output is correct |
14 | Correct | 28 ms | 5080 KB | Output is correct |
15 | Correct | 99 ms | 10680 KB | Output is correct |
16 | Correct | 288 ms | 14164 KB | Output is correct |
17 | Correct | 26 ms | 5080 KB | Output is correct |
18 | Correct | 12 ms | 4696 KB | Output is correct |
19 | Correct | 1 ms | 4444 KB | Output is correct |
20 | Correct | 336 ms | 16088 KB | Output is correct |
21 | Correct | 342 ms | 15776 KB | Output is correct |
22 | Correct | 1 ms | 4440 KB | Output is correct |
23 | Correct | 1 ms | 4444 KB | Output is correct |
24 | Correct | 1 ms | 4444 KB | Output is correct |
25 | Correct | 1 ms | 4444 KB | Output is correct |
26 | Correct | 2 ms | 4444 KB | Output is correct |
27 | Correct | 1 ms | 4444 KB | Output is correct |
28 | Correct | 1 ms | 4444 KB | Output is correct |
29 | Correct | 1 ms | 4444 KB | Output is correct |
30 | Correct | 1 ms | 4444 KB | Output is correct |
31 | Correct | 1 ms | 4444 KB | Output is correct |
32 | Correct | 9 ms | 4696 KB | Output is correct |
33 | Correct | 113 ms | 12304 KB | Output is correct |
34 | Correct | 96 ms | 11604 KB | Output is correct |
35 | Correct | 339 ms | 16040 KB | Output is correct |
36 | Correct | 360 ms | 15852 KB | Output is correct |
37 | Correct | 297 ms | 16212 KB | Output is correct |
38 | Correct | 131 ms | 12116 KB | Output is correct |