Submission #1139715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139715		vladig	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	20 / 100	84 ms	2376 KiB

plaukimo_varzybos

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

#define MAXN 500000

int v[ MAXN + 1 ];

int n, a, b;

//bool canbesplit( int sz, int a, int b )
//{
//    int num = sz / a;
//    int dif = sz % a;
//
//    if( a == b && dif != 0 )
//    {
//        return false;
//    }
//    else if( a == b )
//    {
//        return true;
//    }
//    else
//    {
//        return ( b - a ) * num > dif;
//    }
//}

bool check( int val )
{
    deque<int> dq;
    dq.push_back( -1 );

    int index = a - 1;
    while( index < n && dq.empty( ) == false )
    {
        if( index - dq.front( )  >= a )
        {
            if( index - dq.front( ) <= b && v[ index ] - v[ dq.front( ) + 1 ] <= val )
            {
                dq.push_back( index );
                index++;
            }
            else
            {
                dq.pop_front( );
            }
        }
        else
        {
            index++;
        }
    }

    if( dq.empty( ) == true )
    {
        return false;
    }

    return dq.back( ) == n - 1;
}

int bsearch( )
{
    int left = 0, right = v[ n - 1 ] - v[ 0 ] + 1;
    int answ = right;

    while( left <= right )
    {
        int mid = ( left + right ) / 2;

        if( check( mid ) == true )
        {
            answ = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }

    return answ;
}

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

    std::sort( v, v + n );

    cout << bsearch( );
    return 0;
}

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