Cod sursa(job #230068)

Utilizator katakunaCazacu Alexandru katakuna Data 12 decembrie 2008 21:32:50
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<stdio.h>
#include <algorithm>
#define INF 1<<30 ;
using namespace std;

long long Min,a,b,i,S,n,dx,dy,maxx,maxy,x[50111],y[50111],vix[50111],viy[50111];
long long rez;

int main(){

FILE *f=fopen("tribute.in","r");
fscanf(f,"%lld %lld %lld",&n,&dx,&dy);
maxx=maxy=-1;

  for(i=1;i<=n;i++){
  fscanf(f,"%lld %lld",&x[i],&y[i]);
  vix[x[i]]++;

    if(x[i]>maxx)
    maxx=x[i];
    
  viy[y[i]]++;

    if(y[i]>maxy)
    maxy=y[i];
  }

fclose(f);


sort(x+1,x+1+n);
sort(y+1,y+1+n);

  for(i=1;i<=maxx;i++)
  vix[i]+=vix[i-1];

long long q=dx+x[1];

   for(i=1;i<=n;i++){
     if(x[i]>q)
     S+=x[i]-q;
   }

Min=INF;

i=x[1]+1;

    for(i=x[1]+1;i+dx<=maxx;i++){
    a=i;
    b=i+dx;
    S+=vix[a-1];
    S-=(n - vix[ (b-1) ]);
//    q=1;
       if(S<Min)
       Min=S;
    }

rez=Min;
Min=INF;

  for(i=1;i<=maxy;i++)
  viy[i]+=viy[i-1];

q=dy+y[1];
S=0;
   for(i=1;i<=n;i++){
     if(y[i]>q)
     S+=y[i]-q;
   }

Min=INF;

    for(i=y[1]+1;i+dy<=maxy;i++){
    a=i;
    b=i+dy;
    S+=viy[a-1];
    S-=(n - viy[ (b-1) ]);
//    q=1;
       if(S<Min)
       Min=S;
    }


FILE *g=fopen("tribute.out","w");

rez+=(long long)Min;

   fprintf(g,"%lld",rez);
fclose(g);

return 0;
}