Cod sursa(job #983504)

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

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

    int p1 = 1, p2 = 1;
    long long minX = inf;
    for(int 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;
}

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

    for(int 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;
}