Cod sursa(job #317868)

Utilizator taloibogdanTaloi Bogdan Cristian taloibogdan Data 25 mai 2009 19:18:26
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
long n,lx,ly,sumx[55000],sumy[55000],ax,ay,fx[55000],fy[55000],mmix[55000],mmiy[55000],mmax[55000],mmay[55000],i,mx,my,minsx,minsy;
int main()
{
 freopen("tribute.in","r",stdin);
 freopen("tribute.out","w",stdout);
 scanf("%ld%ld%ld",&n,&lx,&ly);
 sumx[0]=0;
 sumy[0]=0;
 for(i=1;i<=n;++i)
    {scanf("%ld%ld",&ax,&ay);
     if(ax>lx)sumx[0]+=ax-lx;
     if(ay>ly)sumy[0]+=ay-ly;
     fx[ax]++;
     if(ax>mx)mx=ax;
     fy[ay]++;
     if(ay>my)my=ay;}
 for(i=1;i<=mx+1;++i)mmix[i]=mmix[i-1]+fx[i-1];
 for(i=1;i<=my+1;++i)mmiy[i]=mmiy[i-1]+fy[i-1];
 for(i=mx;i;--i)mmax[i]=mmax[i+1]+fx[i+1];
 for(i=my;i;--i)mmay[i]=mmay[i+1]+fy[i+1];
 minsx=sumx[0];
 for(i=1;i<=mx;++i)
    {sumx[i]=sumx[i-1]+mmix[i]-mmax[i+lx-1];
     if(sumx[i]<minsx)minsx=sumx[i];}
 minsy=sumy[0];
 for(i=1;i<=my;++i)
    {sumy[i]=sumy[i-1]+mmiy[i]-mmay[i+ly-1];
     if(sumy[i]<minsy)minsy=sumy[i];}
 printf("%ld\n",minsx+minsy);
 return 0;
}