Cod sursa(job #489659)

Utilizator andreea1coolBobu Andreea andreea1cool Data 3 octombrie 2010 10:27:12
Problema Tribute Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
long long n,m,i,j,k,ok,smin,dx,dy,sx[50010],sy[50010],v1[50010],v2[50010],min1=999999999,min2=999999999,xmin=99999,xmax=-1,ymin=99999,ymax=-1,solx[50010],soly[50010];

int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%lld%lld%lld",&n,&dx,&dy);
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&m,&j);
        v1[m]++;
        v2[j]++;
        if(m<xmin)xmin=m;
        if(m>xmax)xmax=m;
        if(j<ymin)ymin=j;
        if(j>ymax)ymax=j;
    }
    m=0;k=0;
    solx[0]=v1[0];
    soly[0]=v2[0];
    for(i=1;i<=50000;i++)
    {
        solx[i]=solx[i-1]+v1[i];
        soly[i]=soly[i-1]+v2[i];
    }
    for(i=xmin;i<=xmax;i++)
        if(i>xmin+dx)
        {
            sx[xmin]+=v1[i]*(i-xmin-dx);
        }
    if(sx[xmin]<min1)min1=sx[smin];
    for(i=ymin;i<=ymax;i++)
        if(i>ymin+dy)
        {
            sy[ymin]+=v2[i]*(i-ymin-dy);
        }
    if(sy[ymin]<min2)min2=sy[ymin];
    for(i=xmin+1;i<=xmax-dx;i++)
    {
        sx[i]=sx[i-1]+solx[i-1]-(solx[xmax]-solx[i+dx-1]);
        if(sx[i]<min1)min1=sx[i];
    }
    if(sx[xmax-dx]<min1)min1=sx[xmax-dx];
    for(i=ymin+1;i<=ymax-dy;i++)
    {
        sy[i]=sy[i-1]+soly[i-1]-(soly[ymax]-soly[i+dy-1]);
        if(sy[i]<min2)min2=sy[i];
    }
    if(sy[ymax-dy]<min2)min2=sy[ymax-dy];
    if(n==1)printf("0");
    else
    printf("%lld",min1+min2);

    return 0;
    }