Cod sursa(job #940484)

Utilizator matei_cChristescu Matei matei_c Data 16 aprilie 2013 12:49:47
Problema Tribute Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std ;

#define maxn 10001

int n, dx, dy ;

int nrx[maxn], nry[maxn], sume[maxn] ;

int calc(int d, int nr[maxn])
{
    int act = 0 ;

    sume[0] = nr[0] ;

    for(int i = 1; i < maxn; ++i )
        sume[i] = sume[ i - 1 ] + nr[i] ;

    for(int i = d + 1; i < maxn; ++i )
        act += nr[i] * ( i - d ) ;

    int rez = act ;

    for(int i = 1; i + d < maxn; ++i )
    {
        act += sume[ i - 1 ] - ( sume[ maxn - 1 ] - sume[ i + d - 1 ] ) ;

        rez = min( rez, act ) ;
    }

    return rez ;
}

void citire()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);

    cin >> n >> dx >> dy ;

    for(int i = 1; i <= n; ++i )
    {
        int x, y ;

        cin >> x >> y ;

        ++nrx[x] ;
        ++nry[y] ;
    }
}

void afisare()
{
    int sol = calc( dx, nrx ) + calc( dy, nry ) ;

    cout << sol ;
}

int main()
{
    citire() ;

    afisare() ;

    return 0 ;
}