Submission #1140120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140120		andreifilimon	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	0 / 100	0 ms	324 KiB

plaukimo_varzybos

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_valid(int n, const vector<int>& v, int max_diff, int a, int b)
{
    int g, gstart;
    g = gstart = 0;
    for(int i = 0; i < n; i++)
    {
        if(v[i] - v[gstart] > max_diff)
        {
            if(i - gstart < a) return false;
            g++;
            gstart = i;
        }
    }
    if(n - gstart < a) return false;
    g++;

    return g <= (n + b - 1) / b;
}

int main()
{
    int n, a, b;
    cin >> n >> a >> b;
    vector<int> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    sort(v.begin(), v.end());
    int st, dr, mid, ans;
    st = 0, dr = ans = v[n - 1] - v[0];
    while(st <= dr)
    {
        mid = st + (dr - st) / 2;
        if(is_valid(n, v, mid, a, b))
        {
            ans = mid;
            dr = mid - 1;
        }
        else
        {
            st = mid + 1;
        }
    }
    cout << ans << "\n";
    return 0;
}

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