Cod sursa(job #953850)

Utilizator ericptsStavarache Petru Eric ericpts Data 27 mai 2013 17:28:22
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <algorithm>
#include <cstdio>
using namespace std;

const int MAX_N = 50100;

int dx,dy,n;
int x[MAX_N];
int y[MAX_N];

int solve(int * v,int space)
{
    sort(v+1,v+n+1);
    int i,mid = (n+1)/2 , median = v[mid] , ret = 0;

    for(i = 1 ; i <= n ; ++ i)
        ret += abs(v[i]-median);

    int left = mid , right = mid,done;

    while(space && (left > 1 || right < n)){
        if(n - right > left - 1){
            done = min(space,v[right+1] - v[right]);
            space -= done;
            ret -= (n-right) * done;
            ++right;
        }else{
            done = min(space,v[left] - v[left-1]);
            space -= done;
            ret -= (left - 1) * done;
            --left;
        }
    }
    return ret;
}

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);

    int tot = 0;
    tot += solve(y,dy);
    tot += solve(x,dx);

    printf("%d\n",tot);
    return 0;
}