Submission #1140019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140019		c32ardash	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	100 / 100	290 ms	8264 KiB

plaukimo_varzybos

#include <bits/stdc++.h>

using namespace std;

const int NMAX=1e6+5;
int n, a, b, dm, v[NMAX], f[NMAX];

void init_f()
{
    for(int i=0;i<a;i++)
        f[1+i]=1;
}

bool check(int x)
{
    int j=1;
    for(int i=a;i<=n;i++)
    {
        while(v[i]-v[j]>x)
            j++;
        f[1+i]=f[1+i-1];
        if(j-1>i-a)
            continue;
        f[1+i]+=(f[1+i-a]-f[1+max(i-b, j-1)-1]>0);
    }
    return (f[1+n]==f[1+n-1]);
}

int caut_bin()
{
    int r=-1, pas=(1<<19);
    while(pas)
    {
        if(r+pas<=dm)
            if(check(r+pas))
                r+=pas;
        pas/=2;
    }
    return r+1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>a>>b; init_f();
    for(int i=1;i<=n;i++)
        cin>>v[i];
    sort(v+1, v+n+1);
    v[n+1]=2*NMAX;
    dm=v[n]-v[1];
    cout<<caut_bin();
    return 0;
}

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