제출 #1139725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139725		vladig	Swimming competition (LMIO18_plaukimo_varzybos)	C++20	100 / 100	442 ms	6376 KiB

plaukimo_varzybos

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

using namespace std;

#define MAXN 1000001

int v[ MAXN + 1 ];

int n, a, b;

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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40