Pagini recente » Cod sursa (job #804652) | Cod sursa (job #24955) | Cod sursa (job #1716394) | Cod sursa (job #2380568) | Cod sursa (job #2531877)
#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;
}