Cod sursa(job #2568022)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 3 martie 2020 20:17:53
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 5e4 ;
int pt [ NMAX + 5 ] ;
long long dp [ NMAX + 5 ] ;
int n ;

inline int get_low ( int x )
{
    int st = 1 , dr = n , med , last = 0 ;

    while ( st <= dr )
    {
        med = ( st + dr ) >> 1 ;

        if ( pt [ med ] > x )
            dr = med - 1 , last = med ;
        else
            st = med + 1 ;
    }

    return last ;
}

inline int get_high ( int x )
{
    int st = 1 , dr = n , med , last = 0 ;

    while ( st <= dr )
    {
        med = ( st + dr ) >> 1 ;

        if ( pt [ med ] < x )
            st = med + 1 , last = med ;
        else
            dr = med - 1 ;
    }

    return last ;
}

inline long long solve ( int dim )
{
    int i , low , high  ;
    long long mn = 1e12 , val ;

    sort ( pt + 1 , pt + n + 1 ) ;
    for ( i = 1 ; i <= n ; ++ i )
        dp [ i ] = dp [ i - 1 ] + pt [ i ] ;

    for ( i = 0 ; i <= NMAX ; ++ i )
    {
        low = get_low ( i + dim ) ;
        high = get_high ( i ) ;

        val = 0 ;
        if ( low ) val += dp [ n ] - dp [ low - 1 ] - 1LL * ( n - low + 1 ) * ( i + dim ) ;
        if ( high ) val += 1LL * high * i - dp [ high ] ;

        mn = min ( mn , val ) ;
    }

    return mn ;
}

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

    int dimx , dimy , i , a , b ;
    long long ans = 0 ;

    scanf ( "%d%d%d" , & n , & dimx , & dimy ) ;

    for ( i = 1 ; i <= n ; ++ i )
    {
        scanf ( "%d%d" , & a , & b ) ;
        pt [ i ] = a ;
    }

    ans += solve ( dimx ) ;

    freopen ( "tribute.in" , "r" , stdin ) ;

    scanf ( "%d%d%d" , & n , & dimx , & dimy ) ;

    for ( i = 1 ; i <= n ; ++ i )
    {
        scanf ( "%d%d" , & a , & b ) ;
        pt [ i ] = b ;
    }

    ans += solve ( dimy ) ;

    printf ( "%lld" , ans ) ;

    return 0;
}