Cod sursa(job #1259898)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 10 noiembrie 2014 18:08:29
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

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

int n, dx, dy;

vector <int> x, y;

const int MAXN = 50000;

void citire()
{
    in>>n>>dx>>dy;
    for(int i = 1; i <= n; i++)
    {
        int p,q;
        in>>p>>q;
        x.push_back(p);
        y.push_back(q);
    }
}

int sweep( vector <int> &v, int lg )
{

    if( v.size() == 1 )
        return 0;

    sort(v.begin(),v.end() );

    int a = v[0], b = v[0] + lg;
    int last = 0, first = -1;

    int s[MAXN+2];
    s[0] = v[0];
    for(int i = 1; i < n; i++)
        s[i] = s[i-1] + v[i];

    int Smin = 0, aMin = 0;

    for(int i = 0; i < n; i++)
        if( v[i] < a )
            Smin += (a-v[i]);
        else if( b < v[i] )
            Smin += (v[i]-b);

    while( b <= v[n-1] )
    {
        while( v[first+1] < a )
            first++;

        while( last < n  && v[last] <= b )
            last++;

        //dynamic;
        int sLeft, sRight;

        if( first == - 1 )
            sLeft = 0;
        else sLeft = a*(first+1) - s[first];

        if( last == n )
            sRight = 0;
        else sRight = ( s[n-1] - s[last-1] ) - b*( n -  last );//bookmark

        Smin = min(sRight+sLeft,Smin);

        a++, b++;
    }
    return Smin;
}


int main()
{
    citire();
    out<<sweep(x,dx) + sweep(y,dy);
    return 0;
}