Cod sursa(job #1242577)

Utilizator gedicaAlpaca Gedit gedica Data 14 octombrie 2014 18:26:37
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>

using namespace std;

ifstream in( "tribute.in" );
ofstream out( "tribute.out" );

const int NMAX= 50001;

int N, v[2][NMAX];

int dina(int k, int dx, int xmax)
{
    int a=0, b=0, suma=0, mini=0;
    for( int i=xmax; i>dx; --i )
    {
        b+= v[k][i];
        suma+= v[k][i]*( i-dx );
    }
    mini= suma;
    for( int i= 1; i<=xmax; ++i )
    {
        a+= v[k][i-1];
        suma+= a-b;
        if( i+dx<=xmax )
        {
            b-= v[k][i+dx];
        }
        if( suma<mini )
        {
            mini= suma;
        }
    }
    return mini;
}

int main()
{
    int DX, DY, xmax= -1, ymax= -1, x ,y;

    in >> N >> DX >> DY;

    for( int i=0; i<N; ++i )
    {
        in >> x >> y;
        if( x>xmax )
        {
            xmax= x;
        }
        if( y>ymax )
        {
            ymax= y;
        }
        ++v[0][x];
        ++v[1][y];
    }

    out << dina(0, DX, xmax)+dina(1, DY, ymax);
    return 0;
}