Cod sursa(job #343549)

Utilizator mgntMarius B mgnt Data 26 august 2009 11:15:54
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#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;
}