Cod sursa(job #1142498)

Utilizator PatrikStepan Patrik Patrik Data 13 martie 2014 21:30:29
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
    #include<cstdio>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    #define NMAX 50001
    int N , X[NMAX] , Y[NMAX] , Dx , Dy , dr , st ;

    int solve(int v[] ,int  dim)
    {
        sort(v+1,v+N+1);
        int st = 0 , dr , sum_dr = 0 , sum_st = 0 , best ;
        dr  = N;
        while(dr >= 1 && v[dr] > dim)
        {
            sum_dr += v[dr]-dim;
            dr--;
        }
        best = sum_dr;
        st = 1;
        while(!v[st] && st < N)st++;
        for(int i = 1 ; i + dim <= v[N]  ; ++i )
        {
            sum_dr -= N-dr;
            sum_st += st-1;
            while(v[dr] == i+dim && dr < N)dr++;
            while(v[st] == i && st < N)st++;
            best = min(best,sum_dr + sum_st);
        }
        return best;
    }

    int main()
    {
        freopen("tribute.in" , "r" , stdin );
        freopen("tribute.out" , "w" , stdout );
        scanf("%d%d%d" , &N  , &Dx , &Dy);
        for(int i = 1 ; i <= N ; ++i )
            scanf("%d%d" , &X[i] , &Y[i]);
        printf("%d" , solve(X,Dx)+solve(Y,Dy));
        return 0;
    }