Submission #374609

#	Time	Username	Problem	Language	Result	Execution time	Memory
374609		gustason	Swimming competition (LMIO18_plaukimo_varzybos)	C++11	10 / 100	232 ms	10988 KiB

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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40