Cod sursa(job #1591063)

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

const int MAXN = 50005;
const int INF = 1 << 30;

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

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


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


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

void calculare(int v[],int &rasp,int dim, int dst[], int 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)
    {
        int 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;
}