Cod sursa(job #2892377)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 21 aprilie 2022 20:30:34
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin( "tribute.in" );
ofstream fout( "tribute.out" );

unsigned x[ 50005 ];
unsigned y[ 50005 ];
unsigned n, a, b;

unsigned val( unsigned x[], unsigned a ) {
    unsigned k = 0, j = 0, m = ( 1 << 31 );
    unsigned z[ 50005 ] = { 0 };
    unsigned p[ 50005 ], r[ 50005 ];
    sort( x + 1, x + n + 1 );
    
    if( a >= x[ n ] - x[ 1 ] )
        return 0;
    
    for( int i = 1; i <= n; ++i )
        ++z[ x[ i ] + 1 ];
    z[ x[ 1 ] ] = p[ x[ 1 ] ] = r[ x[ 1 ] ] = 0;
    for( int i = x[ 1 ]; i <= x[ n ] - a; ++i ) {
        j += z[ i ];
        p[ i + 1 ] = p[ i ] + j;
        k += z[ x[ n ] - i + 2 ];
        r[ i + 1 ] = r[ i ] + k;
    }

    for( int i = x[ 1 ]; i <= x[ n ] - a; ++i )
        if( m > ( k = p[ i + 1 ] + r[ x[ n ] - a - i + 1 ] ) )
            m = k;
    return m;
}

int main()
{
    fin >> n >> a >> b;
    for( int i = 1; i <= n; ++i )
        fin >> x[ i ] >> y[ i ];
    fout << ( val( x, a ) + val( y, b ) ) << '\n';
    return 0;
}