Submission #374684

#	Time	Username	Problem	Language	Result	Execution time	Memory
374684		gustason	Swimming competition (LMIO18_plaukimo_varzybos)	C++14	100 / 100	552 ms	13208 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) {
    queue<int> q;
    q.push(-1);

    int i = 0;
    while(i < n && !q.empty()) {
        int v = q.front();
        if (i - v >= l) {
//            cout << i << " " << v << " " << a[i] << " " << a[v+1] << "\n";
            if (i - v <= r && a[i] - a[v+1] <= x) {
                q.push(i);
                i++;
            } else {
                q.pop();
            }
        } else {
            i++;
        }
    } cerr << "\n";

    return !q.empty() && q.back() == n-1;
}
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();
    cout << ans;
    return 0;
}

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