Cod sursa(job #633206)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 noiembrie 2011 09:00:39
Problema Tribute Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 50005
#define lul unsigned long long
int x[N],y[N],n,dx,dy,i;

int c(int a,int b)
{return a<b;}
      
lul h(int x[N],int dx)
{lul k=0,j=0,m=N,z[N]={0},p[N],r[N];
sort(x+1,x+n+1,c);
if(dx>=x[n]-x[1])
      return 0;
for(i=1;i<=n;i++)
      z[x[i]+1]++;
z[x[1]]=p[x[1]]=r[x[1]]=0;
for(i=x[1];i<=x[n]-dx;i++)
      {j+=z[i],p[i+1]=p[i]+j;
      k+=z[x[n]-i+2];
      r[i+1]=r[i]+k;}
for(i=x[1];i<=x[n]-dx;i++)
if(m>(k=p[i+1]+r[x[n]-dx-i+1]))
      m=k;
return m;}

int main()
{FILE *f=fopen("tribute.in","r"),*g=fopen("tribute.out","w");
fscanf(f,"%d%d%d",&n,&dx,&dy);
for(i=1;i<=n;i++)
      fscanf(f,"%d%d",&x[i],&y[i]);
fprintf(g,"%llu",h(x,dx)+h(y,dy));
return 0;}