Pagini recente » Cod sursa (job #90652) | Cod sursa (job #489677)
Cod sursa(job #489677)
#include<stdio.h>
int x[50010],y[50010];//390 kb
short fx[50010],fy[50010];//195 kb
int dsumx[50010],lsumx[50010],dsumy[50010],lsumy[50010];//781 KB
//total 1,366 MB
#define MAXPROB 2500000001
int main()
{
int i,n,xmax=0,ymax=0,mx=0,my=0;
int maxus=0,minus=0,MAXIMUS=0;
freopen("tribute.in","r",stdin);
freopen("tribute.out","w",stdout);
scanf("%d%d%d",&n,&maxus,&minus);
if(maxus<minus)
{
xmax=maxus;
maxus=minus;
minus=xmax;
xmax=0;
}
for(i=0;i<n;++i)
{
scanf("%d%d",x+i,y+i);
fx[x[i]]++;
fy[y[i]]++;
mx+=x[i];
my+=y[i];
if(xmax<x[i])
xmax=x[i];
if(ymax<y[i])
ymax=y[i];//determining upper limmit
}
MAXIMUS=xmax;
if(MAXIMUS<ymax)
MAXIMUS=ymax;
//complexity so far approx 2*n
int xlng,ylng;
int amountx=0,amounty=0;
dsumx[0]=0;
amountx=fx[0];
dsumy[0]=0;
amounty=fy[0];
//generating sums
for(i=1;i<=MAXIMUS;++i)
{
dsumx[i]=dsumx[i-1]+amountx;
if(fx[i])
amountx+=fx[i];
dsumy[i]=dsumy[i-1]+amounty;
if(fy[i])
amounty+=fy[i];
}
lsumx[xmax]=0;
amountx=0;
lsumy[ymax]=0;
amounty=0;
for(i=MAXIMUS;i>=0;--i)
{
lsumx[i]=lsumx[i+1]+amountx;
if(fx[i])
amountx+=fx[i];
lsumy[i]=lsumy[i+1]+amounty;
if(fy[i])
amounty+=fy[i];
}
//complexity so far approx 6*n;
int xsum=0,ysum=0,Xmax=-1,Ymax=-1;
if((double)mx/n<(double)my/n)
{
xlng=minus;
ylng=maxus;
}
else
{
xlng=maxus;
ylng=minus;
}
//generating responses
bool xnv=0,ynv=0,kx,ky;
if(xlng>xmax)
{
kx=1;
Xmax=0;
}
if(ylng>ymax)
{
ky=1;
Ymax=0;
}
for(i=0;i<=MAXIMUS&&(!kx||!ky);++i)
{
xnv=kx;
ynv=ky;
xsum=dsumx[i];
if(i+xlng<=MAXIMUS)
xsum+=lsumx[i+xlng];
else
xnv=1;
ysum=dsumy[i];
if(i+ylng<=MAXIMUS)
ysum+=lsumy[i+ylng];
else
ynv=1;
if(Xmax>xsum||Xmax==-1&&!xnv)
Xmax=xsum;
if(Ymax>ysum||Ymax==-1&&!ynv)
Ymax=ysum;
xsum=ysum=0;
}
//so fac complexity approx 8*n
printf("%d",Xmax+Ymax);
return 0;
}