Cod sursa(job #2157619)

Utilizator Davla2Stancu Vlad Davla2 Data 9 martie 2018 19:20:03
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int n;

int calcul(int v[], int nr[], int d)
{
    sort(v, v+n);
    int dist=0,distmin,nrst=0,nrdr=0;
    for(int i=0; i<n; i++)
    {
        nr[v[i]]++;
        if(v[i]>d)
        {
            dist+=v[i]-d;
            nrdr++;
        }
    }
    distmin=dist;
    //out << 0 << "->" << d << ":\t" << nrst << "\t" << nrdr << "\t" << dist << "\n";
    for(int i=1; i+d<50001; i++)
    {
        nrst+=nr[i-1];
        dist+=nrst-nrdr;
        nrdr-=nr[i+d];
        //out << i << "->" << i + d << ":\t" << nrst << "\t" << nrdr << "\t"  << dist << "\n";
        distmin=min(distmin, dist);
    }
    return distmin;
}

int x[50001],y[50001],dx,dy,nrx[50001],nry[50001];

int main()
{
    in>>n>>dx>>dy;
    for(int i=0; i<n; i++)
    {
        in>>x[i];
        in>>y[i];
    }
    out<<calcul(x, nrx, dx)+calcul(y, nry, dy);
    return 0;
}