Pagini recente » Cod sursa (job #347393) | Cod sursa (job #91126) | Cod sursa (job #347349) | Cod sursa (job #2320555) | Cod sursa (job #350695)
Cod sursa(job #350695)
#include <cstdio>
#define Nmax 50100
int n, dx, dy, x, y, i, mx, my, xmax, ymax;
int X[Nmax], Y[Nmax], Sx[Nmax], Sy[Nmax], Lx[Nmax], Ly[Nmax];
int main () {
FILE *f = fopen ("tribute.in", "r");
FILE *g = fopen ("tribute.out", "w");
fscanf (f, "%d %d %d", &n, &dx, &dy);
for (i = 1; i <= n; i++) {
fscanf (f, "%d %d", &x, &y);
X[x]++; Y[y]++;
if (xmax < x) xmax = x;
if (ymax < y) ymax = y;
}
Sx[0] = X[0];
for (i = 1; i <= xmax; i++)
Sx[i] = Sx[i-1] + X[i];
Sy[0] = Y[0];
for (i = 1; i <= ymax; i++)
Sy[i] = Sy[i-1] + Y[i];
/////////////////////////////////////
for (i = dx+1; i <= xmax; i++)
Lx[0]+= (i - dx) * X[i];
mx = Lx[0];
for (i = 1; i <= xmax - dx; i++) {
Lx[i] = Lx[i-1] - ( Sx[xmax] - Sx[i+dx-1] ) + Sx[i-1];
if (mx > Lx[i]) mx = Lx[i];
}
////////////////////////////////////////
for (i = dy+1; i <= ymax; i++)
Ly[0]+= (i - dy) * Y[i];
my = Ly[0];
for (i = 1; i <= ymax - dy; i++) {
Ly[i] = Ly[i-1] - ( Sy[ymax] - Sy[i+dy-1] ) + Sy[i-1];
if (my > Ly[i]) my = Ly[i];
}
fprintf (g, "%d", mx + my);
fclose (f);
fclose (g);
return 0;
}