Cod sursa(job #1686035)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 12 aprilie 2016 00:03:57
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>

using namespace std;

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

int const mx = 150005;
int L[mx], C[mx];
int dx, dy, n;
long long sol;
long long const oo = 1000000000000000000LL;

void Read()
{
    int i, x, y;
    f>>n>>dx>>dy;
    for(i=1; i<=n; i++){
        f>>x>>y;
        L[x+50002]++;
        C[y+50002]++;
    }
}

void SolveL()
{
    long long i, st, dr, sum, lside, rside, mini;

    st = 1;
    dr = 1 + dx;
    lside = 0;
    rside = n;

    sum = 0;
    for(i=dr+1; i<mx; i++)
        sum += 1LL * L[i] * (i - dr);

    mini = oo;
    st++; dr++;
    for( ; dr < mx; st++, dr++){
        lside += L[st-1];
        sum += (lside - rside);
        rside -= L[dr];
        mini = min(mini, sum);
    }

    sol += mini;
}

void SolveC()
{
    long long i, st, dr, sum, lside, rside, mini;

    st = 1;
    dr = 1 + dy;
    lside = 0;
    rside = n;

    sum = 0;
    for(i=dr+1; i<mx; i++)
        sum += 1LL * C[i] * (i - dr);

    mini = oo;
    st++; dr++;
    for( ; dr < mx; st++, dr++){
        lside += C[st-1];
        sum += (lside - rside);
        rside -= C[dr];
        mini = min(mini, sum);
    }

    sol += mini;
}

int main()
{
    Read();
    SolveL();
    SolveC();
    g<<sol<<"\n";
    return 0;
}