Cod sursa(job #2531877)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 26 ianuarie 2020 20:28:26
Problema Tribute Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 5e1 ;
long long dpr [ NMAX + 5 ] , dpl [ NMAX + 5 ] , dp [ NMAX + 5 ] ;
long long l [ NMAX + 5 ] , c [ NMAX + 5 ] ;

int main()
{
    freopen ( "tribute.in" , "r" , stdin ) ;
    freopen ( "tribute.out" , "w" , stdout ) ;

    long long n , d1 , d2 , i , x , y , poz , sum , ans1 = 1 << 30 , ans2 = 1 << 30 ;

    scanf ( "%lld%lld%lld" , & n , & d1 , & d2 ) ;

    for ( i = 1 ; i <= n ; ++ i )
    {
        scanf ( "%lld%lld" , & x , & y ) ;
        l [ i ] = x ; c [ i ] = y ;
    }

    sort ( l + 1 , l + n + 1 ) ;
    sort ( c + 1 , c + n + 1 ) ;

    for ( i = l [ 1 ] , poz = 0 , sum = 0 ; i <= l [ n ] ; ++ i )
    {
        if ( i == l [ poz + 1 ] )
        {
            ++ poz ;
            sum += i ;
        }

        dpl [ i ] = 1LL * i * poz - sum ;
    }

    for ( i = l [ n ] , sum = 0 , poz = n + 1 ; i >= l [ 1 ] ; -- i )
    {
        if ( i == l [ poz - 1 ] )
        {
            -- poz ;
            sum += i ;
        }

        dpr [ i ] = sum - i * ( n - poz ) ;
    }

    for ( i = l [ 1 ] ; i <= l [ n ] - d1 ; ++ i )
        ans1 = min ( ans1 , dpl [ i ] + dpr [ i + d1 ] ) ;

    for ( i = c [ 1 ] , poz = 0 , sum = 0 ; i <= c [ n ] ; ++ i )
    {
        if ( i == c [ poz + 1 ] )
        {
            ++ poz ;
            sum += i ;
        }

        dpl [ i ] = 1LL * i * poz - sum ;
    }

    for ( i = c [ n ] , sum = 0 , poz = n + 1 ; i >= c [ 1 ] ; -- i )
    {
        if ( i == c [ poz - 1 ] )
        {
            -- poz ;
            sum += i ;
        }

        dpr [ i ] = sum - i * ( n - poz ) ;
    }

    for ( i = c [ 1 ] ; i <= c [ n ] - d2 ; ++ i )
        ans2 = min ( ans2 , dpl [ i ] + dpr [ i + d2 ] ) ;

    printf ( "%lld" , ans1 + ans2 ) ;

    return 0;
}