# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377692 | 2021-03-14T18:53:22 Z | Aldas25 | Swimming competition (LMIO18_plaukimo_varzybos) | C++14 | 435 ms | 12080 KB |
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr) #define FOR(i, a, b) for(int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define pb push_back #define f first #define s second typedef long double ld; typedef long long ll; typedef pair<int, int> pii; typedef pair<int, pii> piii; typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vl; typedef vector<piii> viii; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MAXN = 1000100, MAXK = 23; const ll MOD = 1e9+7; const ll INF = 1e16; const ld PI = asin(1) * 2; void setIO () { FAST_IO; } void setIO (string s) { setIO(); freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } int n, a, b; int t[MAXN]; bool dp[MAXN]; bool check (int x) { int le = 0; dp[0] = true; FOR(i, 1, n) dp[i] = false; FOR(i, a, n) { while (le < i-a && (le < i-b || t[i] - t[le+1] > x || !dp[le])) { le++; } // cout << " x = " << x << " i = " << i << " le = " << le << endl; if (t[i] - t[le+1] <= x && i-b <= le && le <= i-a && dp[le]) dp[i] = true; //cout <<" dp = " << dp[i] << endl; } return dp[n]; } int main() { setIO(); cin >> n >> a >> b; FOR(i, 1, n) cin >> t[i]; sort(t+1, t+n+1); //FOR(i, 0, 10) cout << " i = " << i << " check = " << check(i) << endl; int le = 0, ri = 1e7; while (le < ri) { int mid = (le+ri)/2; if (check(mid)) ri = mid; else le = mid+1; } cout << le << "\n"; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 18 ms | 1004 KB | Output is correct |
3 | Correct | 3 ms | 492 KB | Output is correct |
4 | Correct | 257 ms | 5356 KB | Output is correct |
5 | Correct | 249 ms | 5228 KB | Output is correct |
6 | Correct | 24 ms | 876 KB | Output is correct |
7 | Correct | 220 ms | 4716 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 1 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 0 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 18 ms | 1004 KB | Output is correct |
3 | Correct | 3 ms | 492 KB | Output is correct |
4 | Correct | 257 ms | 5356 KB | Output is correct |
5 | Correct | 249 ms | 5228 KB | Output is correct |
6 | Correct | 24 ms | 876 KB | Output is correct |
7 | Correct | 220 ms | 4716 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 1 ms | 364 KB | Output is correct |
14 | Correct | 1 ms | 364 KB | Output is correct |
15 | Correct | 1 ms | 364 KB | Output is correct |
16 | Correct | 1 ms | 364 KB | Output is correct |
17 | Correct | 1 ms | 364 KB | Output is correct |
18 | Correct | 0 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 1 ms | 364 KB | Output is correct |
21 | Correct | 9 ms | 620 KB | Output is correct |
22 | Correct | 10 ms | 748 KB | Output is correct |
23 | Correct | 16 ms | 876 KB | Output is correct |
24 | Correct | 22 ms | 1260 KB | Output is correct |
25 | Correct | 131 ms | 5868 KB | Output is correct |
26 | Correct | 228 ms | 9864 KB | Output is correct |
27 | Correct | 26 ms | 1260 KB | Output is correct |
28 | Correct | 16 ms | 1004 KB | Output is correct |
29 | Correct | 1 ms | 364 KB | Output is correct |
30 | Correct | 353 ms | 12012 KB | Output is correct |
31 | Correct | 337 ms | 12012 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 18 ms | 1004 KB | Output is correct |
3 | Correct | 3 ms | 492 KB | Output is correct |
4 | Correct | 257 ms | 5356 KB | Output is correct |
5 | Correct | 249 ms | 5228 KB | Output is correct |
6 | Correct | 24 ms | 876 KB | Output is correct |
7 | Correct | 220 ms | 4716 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 364 KB | Output is correct |
11 | Correct | 9 ms | 620 KB | Output is correct |
12 | Correct | 10 ms | 748 KB | Output is correct |
13 | Correct | 16 ms | 876 KB | Output is correct |
14 | Correct | 22 ms | 1260 KB | Output is correct |
15 | Correct | 131 ms | 5868 KB | Output is correct |
16 | Correct | 228 ms | 9864 KB | Output is correct |
17 | Correct | 26 ms | 1260 KB | Output is correct |
18 | Correct | 16 ms | 1004 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Correct | 353 ms | 12012 KB | Output is correct |
21 | Correct | 337 ms | 12012 KB | Output is correct |
22 | Correct | 1 ms | 364 KB | Output is correct |
23 | Correct | 1 ms | 364 KB | Output is correct |
24 | Correct | 1 ms | 364 KB | Output is correct |
25 | Correct | 1 ms | 364 KB | Output is correct |
26 | Correct | 1 ms | 364 KB | Output is correct |
27 | Correct | 1 ms | 364 KB | Output is correct |
28 | Correct | 1 ms | 364 KB | Output is correct |
29 | Correct | 0 ms | 364 KB | Output is correct |
30 | Correct | 1 ms | 364 KB | Output is correct |
31 | Correct | 1 ms | 364 KB | Output is correct |
32 | Correct | 12 ms | 876 KB | Output is correct |
33 | Correct | 146 ms | 6444 KB | Output is correct |
34 | Correct | 137 ms | 6268 KB | Output is correct |
35 | Correct | 435 ms | 12080 KB | Output is correct |
36 | Correct | 295 ms | 11972 KB | Output is correct |
37 | Correct | 267 ms | 12012 KB | Output is correct |
38 | Correct | 178 ms | 7404 KB | Output is correct |