Cod sursa(job #1237714)

Utilizator felixiPuscasu Felix felixi Data 4 octombrie 2014 18:27:33
Problema Tribute Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>

using namespace std;

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

const long long NMAX = 50000;
const long long INF  = (1<<30);

long long a[NMAX+1], b[NMAX+1];
long long Sx= 0, Sy= 0;
long long N, X,Y;

int main() {
    in >> N >> X >> Y;
    for( long long i= 1;  i<=N;  ++i ) {
        long long n,m;
        in >> n >> m;
        ++a[n];  ++b[m];
        if( n>X ) Sx+= n-X;
        if( m>Y ) Sy+= m-Y;
    }

    long long Rx= INF, Ry= INF;
    long long S= 0, C= 0, D= 0, st= 1, fn= X+1;
    long long ind;

    for( ind= 0;  ind<=X;  ++ind )  {
        C+= a[ind];
    }
    D= N-C;
    for( ;  S<=D && ind<=N;  ++ind, ++st, ++fn ) {
        S+= a[st-1];
        C-= a[st-1];
        C+= a[fn];
        D-= a[fn];
        Sx-= D;  Sx-= a[fn];
        Sx+= S;
        Rx= min( Rx, Sx );
    }

    S= D= C= 0;
    ind= 0;  st= 1;  fn= Y+1;
    for( ind= 0;  ind<=Y;  ++ind ) {
        C+= b[ind];
    }
    D= N-C;
    for( ;  S<=D && ind<=N;  ++ind, ++st, ++fn )  {
        S+= b[st-1];
        C-= b[st-1];
        C+= b[fn];
        D-= b[fn];
        Sy+= (S-D-b[fn]);
        Ry= min( Ry, Sy );
    }

    out << Rx+Ry << '\n';

    return 0;
}