Cod sursa(job #690865)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 25 februarie 2012 23:32:13
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <algorithm>

#define MAX 50050
#define INF 1000000000

using namespace std;

int oX[MAX], oY[MAX], dX, dY, n;

int detDist(int v[MAX], int d, int start, int stop)
{
    int i, minim, sum = 0;
    for(i = start + d; i <= stop; i++)
        sum += (i - (start + d)) * v[i];
    minim = sum;
    for(i = start + 1; i <= stop; i++)
    {
        v[i] += v[i - 1];
    }
    for(i = start + 1; i + d <= stop; i++)
    {
        sum += v[i - 1];
        sum -= n;
        sum += v[i + d - 1];
        if(sum < minim)
            minim = sum;
    }
    return minim;
}

int main()
{
    freopen("tribute.in", "r", stdin);
    scanf("%d %d %d", &n, &dX, &dY);
    int x, y, maxX = 0, maxY = 0, minX = INF, minY = INF;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &x, &y);
        if(x > maxX) maxX = x;
        if(x < minX) minX = x;
        if(y > maxY) maxY = y;
        if(y < minY) minY = y;
        oX[x]++; oY[y]++;
    }
    fclose(stdin);
    freopen("tribute.out", "w", stdout);
    printf("%d", detDist(oX, dX, minX, maxX) + detDist(oY, dY, minY, maxY));
    return 0;
}