Submission #374609

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
374609	2021-03-07T15:15:02 Z	gustason	Swimming competition (LMIO18_plaukimo_varzybos)	C++11	10 / 100	232 ms	10988 KB

plaukimo_varzybos

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n, l, r;
vector<int> a;
bool poss(int x) {
    int sz = 1, mn = a[0];
    for(int i = 1; i < n; i++) {
        if (a[i] - mn > x || sz == r || (n-i == l && (sz + n-i) > r)) {
            if (sz < l) return false;
            sz = 1;
            mn = a[i];
        } else {
            sz++;
        }
    }
    return sz >= l && sz <= r;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> l >> r;
    a.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    int L = 0, R = 1e6, ans = R;
    while(L <= R) {
        int mid = (L + R) / 2;
        if (poss(mid)) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	15 ms	1388 KB	Output is correct
3	Correct	3 ms	492 KB	Output is correct
4	Correct	232 ms	10988 KB	Output is correct
5	Correct	225 ms	10988 KB	Output is correct
6	Correct	22 ms	1388 KB	Output is correct
7	Correct	205 ms	9964 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

Subtask #2

0 / 20.0

#	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	Incorrect	1 ms	492 KB	Output isn't correct
10	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	15 ms	1388 KB	Output is correct
3	Correct	3 ms	492 KB	Output is correct
4	Correct	232 ms	10988 KB	Output is correct
5	Correct	225 ms	10988 KB	Output is correct
6	Correct	22 ms	1388 KB	Output is correct
7	Correct	205 ms	9964 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	Incorrect	1 ms	492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	15 ms	1388 KB	Output is correct
3	Correct	3 ms	492 KB	Output is correct
4	Correct	232 ms	10988 KB	Output is correct
5	Correct	225 ms	10988 KB	Output is correct
6	Correct	22 ms	1388 KB	Output is correct
7	Correct	205 ms	9964 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	Incorrect	1 ms	492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-