Cod sursa(job #983506)

Utilizator cosmyoPaunel Cosmin cosmyo Data 12 august 2013 00:18:16
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

const long long N = 50001;
const long long inf = 0x3f3f3f;
long long x[N], y[N];
long long solve(long long x[N], long long n, long long dx) {
    sort (x + 1, x + n + 1);
    vector<long long> s(n + 2, 0);
    for(long long i = 1; i <= n; ++i)
    {
        s[i] = s[i - 1] + (long long)x[i];
    }

    long long p1 = 1, p2 = 1;
    long long minX = inf;
    for(long long i = 0; i < N ; ++i)
    {
        while(x[p1] <= i && p1 <= n)
        {
            ++p1;
        }
        while(x[p2] <= i + dx && p2 <= n)
        {
            ++p2;
        }
        long long manDis = ((long long)i * (p1 - 1)) - s[p1 - 1 ] +
                           (s[n] - s[p2 - 1]) -
                           ((long long) (n - p2 + 1) * (i + dx));

        if(manDis < minX)
        {
            minX = manDis;
        }
    }

    return minX;
}

long long main() {
    ifstream cin("tribute.in");
    ofstream cout("tribute.out");
    long long n, dx, dy;
    cin >> n >> dx >> dy;

    for(long long i = 1; i <= n; ++i)
    {
        cin >> x[i] >> y[i];
    }

    long long minX = solve(x, n, dx);
    long long minY = solve(y, n, dy);

    cout << minX + minY << '\n';

    return 0;
}