Cod sursa(job #1591083)

Utilizator BugirosRobert Bugiros Data 5 februarie 2016 19:17:17
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int MAXN = 100005;
const long long INF = 1ll << 62;

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

int n,dx,dy;
int x[MAXN],y[MAXN];
long long rasp_1,rasp_2;


void citire()
{
    in >> n >> dx >> dy;
    for (int i = 1;i <= n;++i)
        in >> x[i] >> y[i];
}


long long dstx[MAXN], ddrx[MAXN], dsty[MAXN], ddry[MAXN];

void calculare(int v[], long long &rasp,int dim, long long dst[], long long ddr[])
{
    sort(v + 1, v + n + 1);
    int poz = 1;
    //int dst[MAXN] = {0}, ddr[MAXN] = {0};
    int cati = 0;
    for (int i = v[1];i < MAXN && poz <= n;++i)//parcurgere stanga
    {
        while(poz <= n && v[poz] < i)
        {
            ++cati;
            ++poz;
        }
        dst[i] = dst[i - 1] + cati;
    }

    poz = n;
    cati = 0;
    for (int i = v[n];i >= 0 && poz > 0;--i)//parcurgere dreapta
    {
        while(poz > 0 && v[poz] > i)
        {
            ++cati;
            --poz;
        }
        ddr[i] = ddr[i + 1] + cati;
    }

    rasp = INF;
    for (int i = 0;i + dim <= v[n];++i)
    {
        long long nr = dst[i] + ddr[i + dim];
        if (nr < rasp)
            rasp = nr;
    }

}

int main()
{
    citire();
    calculare(x,rasp_1,dx,dstx,ddrx);
    calculare(y,rasp_2,dy,dstx,ddry);
    out << rasp_1 + rasp_2 << '\n';
    return 0;
}