Submission #1139714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139714		stanrares	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	0 / 100	0 ms	324 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], f[NMAX], n, a, b;

bool check(int x) {
    int l = 1;
    for (int r = 1; r <= n; r++) {
        while (l <= n && (v[r] - v[l] >= x || r - l + 1 > b)) {
            if (l + 1 == r && v[r] - v[l] > x && v[r + 1] != v[r])
                return false;
            l++;
            if (l > r)
                return false;
        }
    }
    return true;
}

int main() {
    int r = 0, minn = INT_MAX, maxx = INT_MIN;
    cin >> n >> a >> b;

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

    for (int i = 2; i <= n; i++) {
        minn = min(minn, v[i] - v[i - 1]);
        maxx = max(maxx, v[i] - v[i - 1]);
    }
    int st = minn, dr = maxx;
    while (st <= dr) {
        int mid = (st + dr) / 2;
        if (check(mid)) {
            r = mid;
            dr = mid - 1;
        } else st = mid + 1;
    }
    cout << r;
    return 0;
}

/*
8 3 5
1 1 1 5 6 6 7 11

8 3 5
1 5 8 8 1 1 8 10
*/

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