Cod sursa(job #1316814)

Utilizator dariusdariusMarian Darius dariusdarius Data 14 ianuarie 2015 10:36:12
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <algorithm>
#include <fstream>
using namespace std;

const int INFINITE = 1.e9;
const int MAX_N = 50000;

int n, vx[MAX_N + 1], vy[MAX_N + 1];
int sp[MAX_N + 1];

inline int solve(int v[MAX_N + 1], int length) {
    sort(v + 1, v + n + 1);
    int i = 0, j = 0, answer = INFINITE;
    for (int i = 1; i <= n; ++ i) {
        sp[i] = sp[i - 1] + v[i];
    }
    for (int start = 0; start + length <= MAX_N; ++ start) {
        while (i < n && v[i + 1] < start) {
            ++ i;
        }
        while (j < n && v[j + 1] < start + length) {
            ++ j;
        }
        answer = min(answer, start * i - sp[i] + (sp[n] - sp[j]) - (start + length) * (n - j));
    }
    return answer;
}

int main() {
    ifstream fin("tribute.in");
    ofstream fout("tribute.out");
    int x, y;
    fin >> n >> x >> y;
    for (int i = 1; i <= n; ++ i) {
        fin >> vx[i] >> vy[i];
    }
    fout << solve(vx, x) + solve(vy, y) << "\n";
    return 0;
}