Cod sursa(job #694380)

Utilizator informatician28Andrei Dinu informatician28 Data 27 februarie 2012 20:34:09
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include<fstream> 
#define DIM 50005 
#define DIM2 50010
#define INF 0x3f3f3f3f
using namespace std; 

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

long long A[DIM2], B[DIM2];
int X[DIM2], Y[DIM2], T[DIM2];
int N, dx, dy; 

long long solve()
{
    int i, s;
    for(i = 0; i <= DIM; i++)
        A[i] = B[i] = 0;
    s = 0;
    for(i = 1; i <= DIM; i++)
    {
        s += T[i-1];
        A[i] = A[i-1] + s;
    }
    s = 0;
    for(i = DIM-1; i >= 0; i--)
    {
        s += T[i+1]; 
        B[i] = B[i+1] + s;
    }
    long long M = (long long) DIM2*DIM2;
    for(i = 0; i + dx <= DIM; i++)
    {
        A[i] += B[i+dx];
        if( A[i] < M )
            M = A[i];
    }
    return M;
}
int main()
{
    int i;
    
    in >> N >> dx >> dy; 
    for(i = 1; i <= N; i++)
    {
        in >> X[i] >> Y[i];
        T[X[i]]++;
    }
    long long sol = solve();
    for(i = 0; i <= DIM; i++)
            T[i] = 0;
    
    for(i = 1; i <= N; i++)
        T[Y[i]]++;
    dx = dy;
    sol += solve(); 
    out << sol << '\n';
    return 0;
}