Cod sursa(job #171813)

Utilizator stefanrStefan Ruseti stefanr Data 5 aprilie 2008 10:41:48
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include<fstream.h>
ifstream fin("tribute.in");
ofstream fout("tribute.out");

struct stare
{long long nrst,nrdr,dst,ddr;}a[50001],b[50001];

struct pct
{long long x,y;}s,max,min,suma;

long long x[50001],y[50001],n,dx,dy,inf=2000000000000

int main()
{fin>>n>>dx>>dy;
int i;
min.x=min.y=inf;
s.x=s.y=inf;
for(i=1;i<=n;i++)
 {fin>>s.x>>s.y;
  x[s.x]++;
  y[s.y]++;
  suma.x+=s.x;
  suma.y+=s.y;
  if(s.x>max.x) max.x=s.x;
  if(s.y>max.y) max.y=s.y;
  if(s.x<min.x) min.x=s.x;
  if(s.y<min.y) min.y=s.y;
 }
suma.x-=n*min.x;
suma.y-=n*min.y;
a[min.x].nrdr=n-x[min.x];
a[min.x].ddr=suma.x;
for(i=min.x+1;i<=max.x;i++)
 {a[i].dst=a[i-1].dst+n-a[i-1].nrdr;
  a[i].ddr=a[i-1].ddr-a[i-1].nrdr;
  a[i].nrst=n-a[i-1].nrdr;
  a[i].nrdr=a[i-1].nrdr-x[i];
 }
b[min.y].nrdr=n-y[min.y];
b[min.y].ddr=suma.y;
for(i=min.y+1;i<=max.y;i++)
 {b[i].dst=b[i-1].dst+n-b[i-1].nrdr;
  b[i].ddr=b[i-1].ddr-b[i-1].nrdr;
  b[i].nrst=n-b[i-1].nrdr;
  b[i].nrdr=b[i-1].nrdr-y[i];
 }
s.x=inf;
s.y=inf;
for(i=min.x;i+dx<=max.x;i++)
 if(a[i].dst+a[i+dx].ddr<s.x) s.x=a[i].dst+a[i+dx].ddr;
for(i=min.y;i+dy<=max.y;i++)
 if(b[i].dst+b[i+dy].ddr<s.y) s.y=b[i].dst+b[i+dy].ddr;
fout<<s.x+s.y;
fin.close();
fout.close();
return 0;
}