Cod sursa(job #5884)

Utilizator mariusdrgdragus marius mariusdrg Data 15 ianuarie 2007 21:11:11
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include<stdio.h>
#include<algorithm>


using namespace std;

const int maxn  = 80000;

long long x;
long long y;
long long x1[maxn];
long long y1[maxn];
long long ind[maxn];
long long ind1[maxn];
long long s[maxn];
long long s1[maxn];
long long sum;
long long sum2;
long long nrd;
long long nrs;
long long i;
long long j;
long long l1;
long long l2;
long long n;



bool cmpf(const long long a,const long long b)
{
        return x1[a]<x1[b];


}

bool cmpf2(const long long a,const long long b)
{
        return y1[a]<y1[b];
}

int main()
{
        freopen("tribute.in","r",stdin);
        freopen("tribute.out","w",stdout);
        scanf("%lld %lld %lld",&n,&x,&y);
        for(i=1;i<=n;i++)
        {
                scanf("%lld %lld",&x1[i],&y1[i]);
                ind[i]=i;
                ind1[i]=i;
        }
        sort(ind+1,ind+n+1,cmpf);
        sort(ind1+1,ind1+n+1,cmpf2);
        for(j=n;j>0;j--)
        {
                if (x1[ind[j]]<=x) break;
                sum+=x1[ind[j]]-x;
        }
        nrd=n-j;
        nrs=0;
        l2=j+1;
        l1=1;
        s[0]=sum;
        for(i=1;i<=50000;i++)
        {
                while(x1[ind[l1]]<i&&l1<=n)
                {
                        nrs++;
                        l1++;
                }
                s[i]=s[i-1]-nrd;
                s[i]+=nrs;
                while(x1[ind[l2]]<=i+x&&l2<=n)
                {
                        nrd--;
                        l2++;
                }

        }
        sum2=0;
        for(j=n;j>0;j--)
        {
                if (y1[ind1[j]]<=y) break;
                sum2+=y1[ind1[j]]-y;
        }
        nrd=n-j;
        nrs=0;
        l2=j+1;
        l1=1;
        s1[0]=sum2;
        for(i=1;i<=50000;i++)
        {
                while(y1[ind1[l1]]<i&&l1<=n)
                {
                        nrs++;
                        l1++;
                }
                s1[i]=s1[i-1]-nrd;
                s1[i]+=nrs;
                while(y1[ind1[l2]]<=i+y&&l2<=n)
                {
                        nrd--;
                        l2++;
                }

        }
        long long min = -1, min2 = -1;
        for(i=1;i<=50000;i++)
        {
                if (s[i]<min||min==-1) min=s[i];
        }
        for(i=1;i<=50000;i++)
        {
                if (s1[i]<min2||min2==-1) min2=s1[i];
        }
        printf("%lld\n",min+min2);
        return 0;
}