Cod sursa(job #1741219)

Utilizator LucianTLucian Trepteanu LucianT Data 13 august 2016 12:59:05
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <bits/stdc++.h>
#define maxN 50000
#define INF (1LL<<45)
using namespace std;
struct point
{
    int X,Y;
}v[maxN];
int n,i,ist,idr,dr,st,sum[maxN],dx,dy;
long long aux1,aux2,solx=INF,soly=INF;
bool cmpx(point a,point b)
{
    return a.X<b.X;
}
bool cmpy(point a,point b)
{
    return a.Y<b.Y;
}
void sweepx()
{
    int i;
    sort(v+1,v+n+1,cmpx);
    for(i=1;i<=n;i++)
        sum[i]=sum[i-1]+v[i].X;
    ist=idr=1;
    solx=INF;
    for(st=0,dr=dx;dr<=maxN;st++,dr++)
    {
        while(ist<=n && v[ist].X<=st)
            ist++;
        while(idr<=n && v[idr].X<=dr)
            idr++;
        aux1=(ist-1)*st-sum[ist-1];
        if(idr>n)
            aux2=0LL;
        else aux2=sum[n]-sum[idr-1]-(n-idr+1)*dr;
        solx=min(solx,aux1+aux2);
    }
}
void sweepy()
{
    int i;
    sort(v+1,v+n+1,cmpy);
    for(i=1;i<=n;i++)
        sum[i]=sum[i-1]+v[i].Y;
    ist=idr=1;
    soly=INF;
    for(st=0,dr=dy;dr<=maxN;st++,dr++)
    {
        while(ist<=n && v[ist].Y<=st)
            ist++;
        while(idr<=n && v[idr].Y<=dr)
            idr++;
        aux1=(ist-1)*st-sum[ist-1];
        if(idr>n)
            aux2=0;
        else aux2=sum[n]-sum[idr-1]-(n-idr+1)*dr;
        soly=min(soly,aux1+aux2);
    }
}
int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d %d %d",&n,&dx,&dy);
    for(i=1;i<=n;i++)
        scanf("%d %d",&v[i].X,&v[i].Y);
    sweepx();
    sweepy();
    printf("%lld",solx+soly);
    return 0;
}