제출 #1139679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139679		vladig	Monthly railway pass (LMIO18_menesinis_bilietas)	C++20	0 / 100	8 ms	2116 KiB

menesinis_bilietas

#include <iostream>
#include <algorithm>

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 )
{
    int index = 1, prevind = 0;
    while( index < n )
    {
        if( v[ index ] - v[ index - 1 ] > val )
        {
            if( canbesplit( index - prevind, a, b ) == false )
            {
                return false;
            }
            prevind = index;
        }

        index++;
    }

    return canbesplit( n - prevind, a, b );
}

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: 0 / 6
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35
• Subtask 5: 0 / 19