# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
247266 | 2020-07-11T08:32:30 Z | Nightlight | Swimming competition (LMIO18_plaukimo_varzybos) | C++14 | 1048 ms | 62308 KB |
#include <bits/stdc++.h> using namespace std; int N, A, B; int arr[1000005]; vector<int> pen[1000005]; bitset<1000001> can; int p, cnt, pos; bool check(int now) { // cout << now << "\n"; p = 1; while(arr[p] - arr[1] <= now) p++; if(p <= A) return 0; can = 0; can[0] = 1; cnt = 0; pen[p].emplace_back(0); for(int i = A; i <= N; i++) { if(can[i - A]) cnt++; if(i > B && can[i - B - 1]) cnt--; while(!pen[i].empty()) { pos = pen[i].back(); if(i - B <= pos && pos <= i - A) cnt--; can[pos] = 0; pen[i].pop_back(); } // cout << i << " " << cnt << "\n"; if(cnt > 0) { can[i] = 1; if(i < N) while(arr[p] - arr[i + 1] <= now) p++; if(p != i) pen[p].emplace_back(i); else can[i] = 0; } } // cout << "\n"; pen[N + 1].clear(); return can[N]; } int main() { scanf("%d %d %d", &N, &A, &B); for(int i = 1; i <= N; i++) { scanf("%d", &arr[i]); } sort(arr + 1, arr + N + 1); // for(int i = 1; i <= N; i++) { // cout << arr[i] << " "; // } // cout << "\n"; arr[N + 1] = 1e9; int l = 0, r = 1000000, ans; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) { r = mid - 1; ans = mid; }else l = mid + 1; } printf("%d\n", ans); cin >> N; } /* 8 2 2 1 5 8 8 1 1 8 1000000 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23936 KB | Output is correct |
2 | Correct | 41 ms | 25080 KB | Output is correct |
3 | Correct | 25 ms | 24320 KB | Output is correct |
4 | Correct | 574 ms | 54900 KB | Output is correct |
5 | Correct | 361 ms | 35960 KB | Output is correct |
6 | Correct | 62 ms | 28280 KB | Output is correct |
7 | Correct | 320 ms | 35064 KB | Output is correct |
8 | Correct | 19 ms | 23936 KB | Output is correct |
9 | Correct | 18 ms | 24004 KB | Output is correct |
10 | Correct | 19 ms | 23936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23936 KB | Output is correct |
2 | Correct | 18 ms | 24004 KB | Output is correct |
3 | Correct | 19 ms | 23936 KB | Output is correct |
4 | Correct | 19 ms | 23936 KB | Output is correct |
5 | Correct | 19 ms | 23936 KB | Output is correct |
6 | Correct | 19 ms | 23936 KB | Output is correct |
7 | Correct | 19 ms | 23936 KB | Output is correct |
8 | Correct | 24 ms | 23936 KB | Output is correct |
9 | Correct | 19 ms | 23936 KB | Output is correct |
10 | Correct | 22 ms | 23936 KB | Output is correct |
11 | Correct | 19 ms | 23936 KB | Output is correct |
12 | Correct | 19 ms | 23936 KB | Output is correct |
13 | Correct | 18 ms | 23936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23936 KB | Output is correct |
2 | Correct | 41 ms | 25080 KB | Output is correct |
3 | Correct | 25 ms | 24320 KB | Output is correct |
4 | Correct | 574 ms | 54900 KB | Output is correct |
5 | Correct | 361 ms | 35960 KB | Output is correct |
6 | Correct | 62 ms | 28280 KB | Output is correct |
7 | Correct | 320 ms | 35064 KB | Output is correct |
8 | Correct | 19 ms | 23936 KB | Output is correct |
9 | Correct | 18 ms | 24004 KB | Output is correct |
10 | Correct | 19 ms | 23936 KB | Output is correct |
11 | Correct | 35 ms | 25216 KB | Output is correct |
12 | Correct | 38 ms | 25084 KB | Output is correct |
13 | Correct | 66 ms | 25968 KB | Output is correct |
14 | Correct | 107 ms | 27640 KB | Output is correct |
15 | Correct | 303 ms | 37960 KB | Output is correct |
16 | Correct | 777 ms | 55620 KB | Output is correct |
17 | Correct | 99 ms | 27512 KB | Output is correct |
18 | Correct | 52 ms | 25760 KB | Output is correct |
19 | Correct | 19 ms | 23936 KB | Output is correct |
20 | Correct | 1014 ms | 62280 KB | Output is correct |
21 | Correct | 1048 ms | 62280 KB | Output is correct |
22 | Correct | 19 ms | 23936 KB | Output is correct |
23 | Correct | 19 ms | 23936 KB | Output is correct |
24 | Correct | 19 ms | 23936 KB | Output is correct |
25 | Correct | 19 ms | 23936 KB | Output is correct |
26 | Correct | 24 ms | 23936 KB | Output is correct |
27 | Correct | 19 ms | 23936 KB | Output is correct |
28 | Correct | 22 ms | 23936 KB | Output is correct |
29 | Correct | 19 ms | 23936 KB | Output is correct |
30 | Correct | 19 ms | 23936 KB | Output is correct |
31 | Correct | 18 ms | 23936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23936 KB | Output is correct |
2 | Correct | 41 ms | 25080 KB | Output is correct |
3 | Correct | 25 ms | 24320 KB | Output is correct |
4 | Correct | 574 ms | 54900 KB | Output is correct |
5 | Correct | 361 ms | 35960 KB | Output is correct |
6 | Correct | 62 ms | 28280 KB | Output is correct |
7 | Correct | 320 ms | 35064 KB | Output is correct |
8 | Correct | 19 ms | 23936 KB | Output is correct |
9 | Correct | 18 ms | 24004 KB | Output is correct |
10 | Correct | 19 ms | 23936 KB | Output is correct |
11 | Correct | 35 ms | 25216 KB | Output is correct |
12 | Correct | 38 ms | 25084 KB | Output is correct |
13 | Correct | 66 ms | 25968 KB | Output is correct |
14 | Correct | 107 ms | 27640 KB | Output is correct |
15 | Correct | 303 ms | 37960 KB | Output is correct |
16 | Correct | 777 ms | 55620 KB | Output is correct |
17 | Correct | 99 ms | 27512 KB | Output is correct |
18 | Correct | 52 ms | 25760 KB | Output is correct |
19 | Correct | 19 ms | 23936 KB | Output is correct |
20 | Correct | 1014 ms | 62280 KB | Output is correct |
21 | Correct | 1048 ms | 62280 KB | Output is correct |
22 | Correct | 19 ms | 23936 KB | Output is correct |
23 | Correct | 19 ms | 23936 KB | Output is correct |
24 | Correct | 19 ms | 23936 KB | Output is correct |
25 | Correct | 19 ms | 23936 KB | Output is correct |
26 | Correct | 24 ms | 23936 KB | Output is correct |
27 | Correct | 19 ms | 23936 KB | Output is correct |
28 | Correct | 22 ms | 23936 KB | Output is correct |
29 | Correct | 19 ms | 23936 KB | Output is correct |
30 | Correct | 19 ms | 23936 KB | Output is correct |
31 | Correct | 18 ms | 23936 KB | Output is correct |
32 | Correct | 55 ms | 25076 KB | Output is correct |
33 | Correct | 482 ms | 37988 KB | Output is correct |
34 | Correct | 300 ms | 38640 KB | Output is correct |
35 | Correct | 966 ms | 62308 KB | Output is correct |
36 | Correct | 460 ms | 51032 KB | Output is correct |
37 | Correct | 426 ms | 42548 KB | Output is correct |
38 | Correct | 433 ms | 45908 KB | Output is correct |