Cod sursa(job #171685)

Utilizator stefanrStefan Ruseti stefanr Data 4 aprilie 2008 20:01:33
Problema Tribute Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include<fstream.h>
ifstream fin("tribute.in");
ofstream fout("tribute.out");

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

struct pct
{int x,y;}s,p,pi,pf,max,min,suma;

int x[50001],y[50001],n,dx,dy,inf=100000;

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>>p.x>>p.y;
  x[p.x]++;
  y[p.y]++;
  suma.x+=p.x;
  suma.y+=p.y;
  if(p.x>max.x) max.x=p.x;
  if(p.y>max.y) max.y=p.y;
  if(p.x<min.x) min.x=p.x;
  if(p.y<min.y) min.y=p.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];
  if(a[i].dst+a[i].ddr<s.x)
   {s.x=a[i].dst+a[i].ddr;
    p.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];
  if(b[i].dst+b[i].ddr<s.y)
   {s.y=b[i].dst+b[i].ddr;
    p.y=i;
   }
 }
pi=pf=p;
s.x=a[p.x].dst+a[p.x].ddr;
s.y=b[p.y].dst+b[p.y].ddr;
for(i=1;i<=dx;i++)
 {if(pf.x==max.x) s.x=a[--pi.x].dst;
  else
   if(pi.x==min.x) s.x=a[++pf.x].ddr;
   else
    if(a[pi.x-1].dst-a[pi.x].dst<a[pf.x+1].ddr-a[pf.x].ddr) s.x+=a[pi.x-1].dst-a[pi.x--].dst;
    else s.x+=a[pf.x+1].ddr-a[pf.x++].ddr;
 }
for(i=1;i<=dy;i++)
 {if(pf.y==max.y) s.y+=b[pi.y-1].dst-b[pi.y--].dst;
  else
   if(pi.y==min.y) s.y+=b[pf.y+1].ddr-b[pf.y++].ddr;
   else
    if(b[pi.y-1].dst-b[pi.y].dst<b[pf.y+1].ddr-b[pf.y].ddr) s.y+=b[pi.y-1].dst-b[pi.y--].dst;
    else s.y+=b[pf.y+1].ddr-b[pf.y++].ddr;
 }
fout<<s.x+s.y;
fin.close();
fout.close();
return 0;
}