Cod sursa(job #1904340)

Utilizator robx12lnLinca Robert robx12ln Data 5 martie 2017 14:39:38
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<fstream>
#include<cstring>
#define m 50000
using namespace std;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
int Dx, Dy, n, a, b, x[50005], y[50005];
long long D1[m + 5];
long long D2[m + 5];
int last[m + 5], nr[m + 5];

long long solve( int f[], int dist ){
    memset( D1, 0, sizeof( D1 ) );
    memset( D2, 0, sizeof( D2 ) );
    memset( last, 0, sizeof( last ) );
    memset( nr, 0, sizeof( nr ) );
    long long minim = (1LL<<63) - 1;
    for( int i = 1; i <= m; i++ ){
        D1[i] = D1[i - 1] + nr[i - 1] * ( i - last[i - 1] );
        nr[i] = nr[i - 1] + f[i];
        last[i] = i;
    }
    memset( last, 0, sizeof( last ) );
    memset( nr, 0, sizeof( nr ) );
    for( int i = m; i >= 1; i-- ){
        D2[i] = D2[i + 1] + nr[i + 1] * ( last[i + 1] - i );
        nr[i] = f[i] + nr[i + 1];
        last[i] = i;
    }
    for( int i = 1; i <= m; i++ ){
        minim = min( D1[i] + D2[i + dist], minim );
    }
    return minim;
}

int main(){
    fin >> n >> Dx >> Dy;
    for( int i = 1; i <= n; i++ ){
        fin >> a >> b;
        x[a + 1]++;
        y[b + 1]++;
    }
    fout << solve( x, Dx ) + solve( y, Dy );
    return 0;
}