Cod sursa(job #1364268)

Utilizator PaueyPaula Nicoleta Gradu Pauey Data 27 februarie 2015 16:23:39
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <algorithm>
#include <fstream>
#include <iostream>
using namespace std;

const int MAXN = 50001;
const int inf = 1.e9;

int px[MAXN], py[MAXN], sp[MAXN], N, Dx, Dy;

inline int sol(int v[MAXN], int L) {
    int ans = inf;
    for(int i = 1; i <= N; ++i)
        sp[i] = sp[i - 1] + v[i];
    int st = 0, dr = 0;
    for(int l = 0; l + L <= MAXN; ++l) {
        while(st < N && v[st + 1] < l)
            ++st;
        while(dr < N && v[dr + 1] < l + L)
            ++dr;
        ans = min(ans, l * st - sp[st] + sp[N] - sp[dr] - (l + L) * (N - dr));
    }
    return ans;
}

int main()
{
    ifstream cin("tribute.in");
    ofstream cout("tribute.out");
    cin >> N >> Dx >> Dy;
    for(int i = 1; i <= N; ++i)
        cin >> px[i] >> py[i];
    sort(px + 1, px + N + 1);
    sort(py + 1, py + N + 1);
    cout << sol(px, Dx) + sol(py, Dy);
    return 0;
}