# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377690 | 2021-03-14T18:52:25 Z | Aldas25 | Swimming competition (LMIO18_plaukimo_varzybos) | C++14 | 266 ms | 12012 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 | 384 KB | Output is correct |
2 | Correct | 18 ms | 876 KB | Output is correct |
3 | Correct | 3 ms | 364 KB | Output is correct |
4 | Correct | 252 ms | 8428 KB | Output is correct |
5 | Correct | 266 ms | 12012 KB | Output is correct |
6 | Correct | 24 ms | 1516 KB | Output is correct |
7 | Correct | 225 ms | 10860 KB | Output is correct |
8 | Correct | 0 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 | 0 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 | 0 ms | 364 KB | Output is correct |
5 | Correct | 0 ms | 364 KB | Output is correct |
6 | Correct | 0 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 | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Incorrect | 1 ms | 364 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 18 ms | 876 KB | Output is correct |
3 | Correct | 3 ms | 364 KB | Output is correct |
4 | Correct | 252 ms | 8428 KB | Output is correct |
5 | Correct | 266 ms | 12012 KB | Output is correct |
6 | Correct | 24 ms | 1516 KB | Output is correct |
7 | Correct | 225 ms | 10860 KB | Output is correct |
8 | Correct | 0 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 | 0 ms | 364 KB | Output is correct |
13 | Correct | 0 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 | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Incorrect | 1 ms | 364 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 18 ms | 876 KB | Output is correct |
3 | Correct | 3 ms | 364 KB | Output is correct |
4 | Correct | 252 ms | 8428 KB | Output is correct |
5 | Correct | 266 ms | 12012 KB | Output is correct |
6 | Correct | 24 ms | 1516 KB | Output is correct |
7 | Correct | 225 ms | 10860 KB | Output is correct |
8 | Correct | 0 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 | 0 ms | 364 KB | Output is correct |
13 | Correct | 0 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 | 1 ms | 364 KB | Output is correct |
19 | Correct | 1 ms | 364 KB | Output is correct |
20 | Incorrect | 1 ms | 364 KB | Output isn't correct |