Submission #1139717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139717		stanrares	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	10 / 100	248 ms	4328 KiB

plaukimo_varzybos

#include <bits/stdc++.h>
using namespace std;

#define NMAX 1000005
#define MOD 1000000007
#define ll long long
#define pb push_back

int v[NMAX], n, a, b;

bool check(int x) {
    int groups = 0, start = 1;

    for (int i = 1; i <= n; i++) {
        if (v[i] - v[start] > x || i - start + 1 > b) {
            if (i - start < a) {
                return false;
            }
            groups++;
            start = i;
        }
    }
    if (n - start + 1 < a) {
        return false;
    }
    groups++;
    return groups <= (n / a);
}

int main() {
    cin >> n >> a >> b;

    for (int i = 1; i <= n; i++) cin >> v[i];
    sort(v + 1, v + 1 + n);

    int left = 0, right = v[n] - v[1], ans = right;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << ans;
    return 0;
}

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