Cod sursa(job #1257591)

Utilizator DorelBarbuBarbu Dorel DorelBarbu Data 7 noiembrie 2014 22:22:28
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <iterator>
using namespace std;

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

const int MAXN = 50000;

long long N, DX, DY, px[MAXN+1], py[MAXN+1];

void citire()
{
    in>>N>>DX>>DY;
    for(int i = 1; i <= N; i++)
        in>>px[i]>>py[i];
}

long long sweep(long long p[MAXN+1], long long lg)
{
    long long sp[MAXN+1];

    sort(p+1,p+N+1);

    sp[0] = 0;

    for(int i = 1; i <= N; i++)
        sp[i] = sp[i-1] + p[i];

    //for(int i = 1; i <= N; i++)
      //  cout<<p[i]<<' ';
    //cout<<endl<<endl;
    long long first, last;

    deque <int> E;

    long long i = 1;

    while( p[i] <= p[1] + lg )
        E.push_back(i++);

    long long a = p[E.front()], b = p[1] + lg;
    long long smin = 2000000;

    while( b <= p[N] )
    {
        if( E.empty() == false )
        {
            int sc = ( sp[N] - sp[ E.back() ] - b*(N-E.back()) )+( a*(E.front()-1) - sp[ E.front() - 1] );
            if( sc < smin )
                smin = sc;
            //cout<<a<<' '<<b<<' '<<sc<<' '<<' ';
        }
         //for( deque <int>::iterator i = E.begin(); i != E.end(); i++)
           // cout<<*i<<' ';
        //cout<<endl;
        a++;
        b++;
        while( p[ E.front() ]  < a && E.empty() == false )
            E.pop_front();

        while( p[ E.back() + 1 ] <= b && E.back() + 1 <= N )
            E.push_back( E.back() + 1 );


    }

    return smin;

}

int main()
{
    citire();
    out<<sweep(py,DY)+sweep(px,DX);
    return 0;
}