Cod sursa(job #1474476)

Utilizator andrettiAndretti Naiden andretti Data 22 august 2015 01:29:28
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<stdio.h>
#include<algorithm>
#define ub upper_bound
#define maxn 50005
#define inf 1LL<<62
using namespace std;

struct Point{int x,y;} a[maxn];
int n,Dx,Dy;
long long s[maxn],MinX=inf,MinY=inf;

void read()
{
    scanf("%d %d %d",&n,&Dx,&Dy);
    for(int i=1;i<=n;i++)
     scanf("%d %d",&a[i].x,&a[i].y);
}

bool cmpx(const Point &A,const Point &B){
    return A.x<B.x;
}

bool cmpy(const Point &A,const Point &B){
    return A.y<B.y;
}

void solve()
{
    int L,R;
    long long cnt;

    sort(a+1,a+n+1,cmpx);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].x;

    L=0;
    for(R=1;R<=n && a[R].x<=Dx;R++);
    for(int i=0;i<=a[n].x;i++)
    {
        while(R<=n && i+Dx>=a[R].x) R++;
        while(L+1<=n && a[L+1].x<i) L++;

        cnt=1LL*L*i-s[L]+s[n]-s[R-1]-1LL*(n-R+1)*(i+Dx);
        MinX=min(MinX,cnt);
    }

    sort(a+1,a+n+1,cmpy);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i].y;

    L=0;
    for(R=1;R<=n && a[R].y<=Dy;R++);
    for(int i=0;i<=a[n].y;i++)
    {
        while(R<=n && i+Dy>=a[R].y) R++;
        while(L+1<=n && a[L+1].y<i) L++;

        cnt=1LL*L*i-s[L]+s[n]-s[R-1]-1LL*(n-R+1)*(i+Dy);
        MinY=min(MinY,cnt);
    }
}

int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);

    read();
    solve();
    printf("%lld",MinX+MinY);

    fclose(stdin);
    fclose(stdout);
    return 0;
}