# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
214765 | 2020-03-26T10:53:58 Z | SamAnd | Swimming competition (LMIO18_plaukimo_varzybos) | C++17 | 547 ms | 15960 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 stg(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 (stg(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 | 5 ms | 384 KB | Output is correct |
2 | Correct | 26 ms | 1932 KB | Output is correct |
3 | Correct | 11 ms | 512 KB | Output is correct |
4 | Correct | 545 ms | 15900 KB | Output is correct |
5 | Correct | 547 ms | 15936 KB | Output is correct |
6 | Correct | 35 ms | 1912 KB | Output is correct |
7 | Correct | 479 ms | 14356 KB | Output is correct |
8 | Correct | 5 ms | 512 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 512 KB | Output is correct |
2 | Correct | 6 ms | 512 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 512 KB | Output is correct |
7 | Correct | 5 ms | 512 KB | Output is correct |
8 | Correct | 5 ms | 384 KB | Output is correct |
9 | Correct | 5 ms | 512 KB | Output is correct |
10 | Correct | 6 ms | 512 KB | Output is correct |
11 | Correct | 5 ms | 384 KB | Output is correct |
12 | Correct | 5 ms | 512 KB | Output is correct |
13 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 26 ms | 1932 KB | Output is correct |
3 | Correct | 11 ms | 512 KB | Output is correct |
4 | Correct | 545 ms | 15900 KB | Output is correct |
5 | Correct | 547 ms | 15936 KB | Output is correct |
6 | Correct | 35 ms | 1912 KB | Output is correct |
7 | Correct | 479 ms | 14356 KB | Output is correct |
8 | Correct | 5 ms | 512 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 14 ms | 896 KB | Output is correct |
12 | Correct | 15 ms | 1024 KB | Output is correct |
13 | Correct | 22 ms | 1280 KB | Output is correct |
14 | Correct | 46 ms | 1664 KB | Output is correct |
15 | Correct | 149 ms | 8568 KB | Output is correct |
16 | Correct | 419 ms | 12792 KB | Output is correct |
17 | Correct | 45 ms | 1664 KB | Output is correct |
18 | Correct | 23 ms | 1280 KB | Output is correct |
19 | Correct | 5 ms | 384 KB | Output is correct |
20 | Correct | 543 ms | 15960 KB | Output is correct |
21 | Correct | 530 ms | 15876 KB | Output is correct |
22 | Correct | 5 ms | 384 KB | Output is correct |
23 | Correct | 5 ms | 384 KB | Output is correct |
24 | Correct | 5 ms | 512 KB | Output is correct |
25 | Correct | 5 ms | 512 KB | Output is correct |
26 | Correct | 5 ms | 384 KB | Output is correct |
27 | Correct | 5 ms | 512 KB | Output is correct |
28 | Correct | 6 ms | 512 KB | Output is correct |
29 | Correct | 5 ms | 384 KB | Output is correct |
30 | Correct | 5 ms | 512 KB | Output is correct |
31 | Correct | 5 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 26 ms | 1932 KB | Output is correct |
3 | Correct | 11 ms | 512 KB | Output is correct |
4 | Correct | 545 ms | 15900 KB | Output is correct |
5 | Correct | 547 ms | 15936 KB | Output is correct |
6 | Correct | 35 ms | 1912 KB | Output is correct |
7 | Correct | 479 ms | 14356 KB | Output is correct |
8 | Correct | 5 ms | 512 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 14 ms | 896 KB | Output is correct |
12 | Correct | 15 ms | 1024 KB | Output is correct |
13 | Correct | 22 ms | 1280 KB | Output is correct |
14 | Correct | 46 ms | 1664 KB | Output is correct |
15 | Correct | 149 ms | 8568 KB | Output is correct |
16 | Correct | 419 ms | 12792 KB | Output is correct |
17 | Correct | 45 ms | 1664 KB | Output is correct |
18 | Correct | 23 ms | 1280 KB | Output is correct |
19 | Correct | 5 ms | 384 KB | Output is correct |
20 | Correct | 543 ms | 15960 KB | Output is correct |
21 | Correct | 530 ms | 15876 KB | Output is correct |
22 | Correct | 5 ms | 384 KB | Output is correct |
23 | Correct | 5 ms | 384 KB | Output is correct |
24 | Correct | 5 ms | 512 KB | Output is correct |
25 | Correct | 5 ms | 512 KB | Output is correct |
26 | Correct | 5 ms | 384 KB | Output is correct |
27 | Correct | 5 ms | 512 KB | Output is correct |
28 | Correct | 6 ms | 512 KB | Output is correct |
29 | Correct | 5 ms | 384 KB | Output is correct |
30 | Correct | 5 ms | 512 KB | Output is correct |
31 | Correct | 5 ms | 384 KB | Output is correct |
32 | Correct | 18 ms | 1280 KB | Output is correct |
33 | Correct | 188 ms | 8568 KB | Output is correct |
34 | Correct | 164 ms | 8444 KB | Output is correct |
35 | Correct | 534 ms | 15840 KB | Output is correct |
36 | Correct | 526 ms | 15864 KB | Output is correct |
37 | Correct | 460 ms | 15864 KB | Output is correct |
38 | Correct | 221 ms | 10104 KB | Output is correct |