Cod sursa(job #1826238)

Utilizator Tiberiu02Tiberiu Musat Tiberiu02 Data 10 decembrie 2016 11:42:25
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
# include <iostream>
# include <fstream>

using namespace std;

# define MAX_N 50001

int xSt[1 + MAX_N + 1];
int xDr[1 + MAX_N + 1];

int ySt[1 + MAX_N + 1];
int yDr[1 + MAX_N + 1];

# define xSt ( xSt + 1 )
# define xDr ( xDr + 1 )
# define ySt ( ySt + 1 )
# define yDr ( yDr + 1 )

int best( int * st, int * dr, int len, int d ) {
    int Best, i;
    Best = 0;
    for ( i = 1; i <= len - d + 1; i ++ ) {
        if ( st[i - 1] + dr[i + d] < st[Best - 1] + dr[Best + d] )
            Best = i;
    }

    return st[Best - 1] + dr[Best + d];
}

int main() {
    ifstream fin( "tribute.in" );
    ofstream fout( "tribute.out" );

    int n, dx, dy, i, j, x, y;

    fin >> n >> dx >> dy;

    for ( i = 0; i < n; i ++ ) {
        fin >> x >> y;

        xSt[x] ++;
        xDr[x] ++;
        ySt[y] ++;
        yDr[y] ++;
    }

    for ( j = 0; j < 2; j ++ ) {
        for ( i = 1; i < MAX_N; i ++ ) {
            xSt[i] += xSt[i - 1];
            ySt[i] += ySt[i - 1];
            xDr[MAX_N - i] += xDr[MAX_N - i + 1];
            yDr[MAX_N - i] += yDr[MAX_N - i + 1];
        }
    }

    fout << best( xSt, xDr, MAX_N, dx + 1 ) + best( ySt, yDr, MAX_N, dy + 1 );

    fin.close();
    fout.close();

    return 0;
}