Pagini recente » Cod sursa (job #343622) | Cod sursa (job #19588) | Cod sursa (job #3177312) | Cod sursa (job #230063) | Cod sursa (job #343549)
Cod sursa(job #343549)
#include <cstdio>
using namespace std;
int const maxz=50000, maxn=50000;
int Z[1+maxz], H[1+maxz], X[maxn], Y[maxn];
// Misc de la 0 pana la 1+maxz si numar pentru
// fiecare miscare cate puncte de la stanga cresc
// cu o unitate, cate de la dreapta scad cu o unitate.
int findMin (int N, int * V, int D) {
int va=0, s, mi, maax=V[0];
for ( s=1; N>s; ++s ) { if (maax<V[s]) { maax=V[s]; } }
// maax<=maxz
for ( s=0; N>s; ++s ) { if (D<V[s]) { va+=(V[s]-D); } } mi=va;
for ( s=0; maax>=s; ++s ) { Z[s]=0; }
for ( s=0; N>s; ++s ) { ++Z[V[s]]; } H[0]=Z[0];
for ( s=1; maax>=s; ++s ) { H[s]=H[s-1]+Z[s]; }
// H[s] - numarul de puncte in intervalul [0..s]
for ( s=1; maax+1>=s; ++s ) {
va+=H[s-1];
if (maax>s+D-1) {
va-=(H[maax]-H[s+D-1]);
}
if (mi>va) { mi=va; }
}
return mi;
}
int main ( ) {
FILE * fi = fopen("tribute.in","r");
int N, DX, DY,s;
fscanf(fi, "%d %d %d", &N, &DX, &DY);
for ( s=0; N>s; ++s ) { fscanf(fi, "%d %d", &X[s], &Y[s]); }
fclose(fi); fi=fopen("tribute.out", "w");
fprintf(fi, "%d\n", findMin(N,X,DX)+findMin(N,Y,DY));
fclose(fi); return 0;
}