Submission #1139726

#TimeUsernameProblemLanguageResultExecution timeMemory
1139726luca_cristianSwimming competition (LMIO18_plaukimo_varzybos)C++20
100 / 100
453 ms6376 KiB
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

const int Nmax = 1e6 + 1;
int v[Nmax];
int n, a, b, sol = -1;

bool ver(int dif)
{
    deque <int> q;
    q.push_back(0);
    int i = a;
    while(i <= n && !q.empty())
    {
        if(i - q.front() >= a)
        {
            if(i - q.front() <= b && v[i] - v[q.front() + 1] <= dif)
            {
                q.push_back(i);
                i++;
            }
            else
                q.pop_front();
        }
        else
            i++;
    }
    if(!q.empty() && q.back() == n)
    {
        return true;
    }
    return false;
}

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

    sort(v + 1, v + n + 1);
    int st = 0, dr = v[n];
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        ///cout << "uite " << mij << '\n';
        if(ver(mij))
        {
            dr = mij - 1, sol = mij;
        }
        else
            st = mij + 1;
    }
    /*if(ver(sol - 1))
        sol--;*/
    cout << sol;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...