Cod sursa(job #1244019)

Utilizator raddudjPogonariu Radu raddudj Data 16 octombrie 2014 18:10:30
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <cstdio>

using namespace std;

const int nmax=50005;
int n;
int v[2][nmax];

int d1(int k, int dx, int xmax)
{
    int l=0, r=0, s=0, min=0;
    for(int i=xmax;i>dx;i--)
    {
        r+=v[k][i];
        s+=v[k][i]*(i-dx);
    }
    min=s;
    for(int i=1;i<=xmax;i++)
    {
        l+=v[k][i-1];
        s+=l-r;
        if(i+dx<=xmax)r-=v[k][i+dx];
        if(s<min)min=s;
    }
    return min;
}

int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);
    int dx, dy;
    int xmax=-1, ymax=-1;
    scanf("%d%d%d", &n, &dx, &dy);
    for(int i=0;i<n;i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if(x>xmax)xmax=x;
        if(y>ymax)ymax=y;
        v[0][x]++;
        v[1][y]++;
    }
    printf("%d\n", d1(0, dx, xmax)+d1(1, dy, ymax));
    return 0;
}