Submission #374625

#	Time	Username	Problem	Language	Result	Execution time	Memory
374625		gustason	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	10 / 100	319 ms	4236 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, mx = a[0], mn = a[0];
    for(int i = 1; i < n; i++) {
        if (abs(a[i] - mx) > x || abs(a[i] - mn) > x || sz == r || (n-i == l && (sz + n-i) > r)) {
            if (sz < l) return false;
            sz = 1;
            mx = a[i];
            mn = a[i];
        } else {
            sz++;
            mx = max(mx, a[i]);
            mn = min(mn, a[i]);
        }
    }
    return sz >= l && sz <= r;
}
int bsearch() {
    int L = 0, R = 1e7, ans = R;
    while(L <= R) {
        int mid = (L + R) / 2;
        if (poss(mid)) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    return ans;
}
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 ans = bsearch();
    reverse(a.begin(), a.end());
    ans = min(ans, bsearch());
    cout << ans;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40