Cod sursa(job #489674)

Utilizator SheepBOYFelix Liviu SheepBOY Data 3 octombrie 2010 12:01:08
Problema Tribute Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#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
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
	for(i=0;i<=MAXIMUS;++i)
	{
		xsum=dsumx[i];
		if(i+xlng<=MAXIMUS)
			xsum+=lsumx[i+xlng];
		
		ysum=dsumy[i];
		if(i+ylng<=MAXIMUS)
			ysum+=lsumy[i+ylng];
		
		if(Xmax>xsum||Xmax==-1)
			Xmax=xsum;
		if(Ymax>ysum||Ymax==-1)
			Ymax=ysum;
		
		xsum=ysum=0;
	}
	//so fac complexity approx 8*n
	printf("%d",Xmax+Ymax);
    return 0;
}