Pagini recente » Cod sursa (job #49368) | Cod sursa (job #397457) | Cod sursa (job #2527071) | Cod sursa (job #3124209) | Cod sursa (job #1904340)
#include<fstream>
#include<cstring>
#define m 50000
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
int Dx, Dy, n, a, b, x[50005], y[50005];
long long D1[m + 5];
long long D2[m + 5];
int last[m + 5], nr[m + 5];
long long solve( int f[], int dist ){
memset( D1, 0, sizeof( D1 ) );
memset( D2, 0, sizeof( D2 ) );
memset( last, 0, sizeof( last ) );
memset( nr, 0, sizeof( nr ) );
long long minim = (1LL<<63) - 1;
for( int i = 1; i <= m; i++ ){
D1[i] = D1[i - 1] + nr[i - 1] * ( i - last[i - 1] );
nr[i] = nr[i - 1] + f[i];
last[i] = i;
}
memset( last, 0, sizeof( last ) );
memset( nr, 0, sizeof( nr ) );
for( int i = m; i >= 1; i-- ){
D2[i] = D2[i + 1] + nr[i + 1] * ( last[i + 1] - i );
nr[i] = f[i] + nr[i + 1];
last[i] = i;
}
for( int i = 1; i <= m; i++ ){
minim = min( D1[i] + D2[i + dist], minim );
}
return minim;
}
int main(){
fin >> n >> Dx >> Dy;
for( int i = 1; i <= n; i++ ){
fin >> a >> b;
x[a + 1]++;
y[b + 1]++;
}
fout << solve( x, Dx ) + solve( y, Dy );
return 0;
}