Cod sursa(job #1434269)

Utilizator movo608Moldovan Andrei movo608 Data 10 mai 2015 14:42:00
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int d1(int k, int dx, int xmax)
{
    int l=0, t=0, s=0, min=0;
    for(int i=xmax;i>dx;i--)
    {
        t+=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-t;
        if(i+dx<=xmax)t-=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;
}