Cod sursa(job #2094674)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 26 decembrie 2017 13:10:00
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int nmax = 5e4;

int n;
pair<int, int> p[nmax + 1];

int v[nmax + 1];
long long s[nmax + 1];

long long solve (int x) {
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; ++ i)
        s[ i ] = s[i - 1] + v[ i ];

    int j = 0, k = 0;

    long long ans = 1LL << 62;
    for (int i = x; i <= nmax; ++ i) {
        while (j + 1 <= n && v[j + 1] < i - x) {
            ++ j;
        }

        while (k <= n && v[ k ] <= i) {
            ++ k;
        }

        long long d = 1LL * (i - x) * j - s[ j ];
        d += (s[ n ] - s[k - 1]) - 1LL * (n - k + 1) * i;

        ans = min(ans, d);
    }
    return ans;
}

int main () {
    int x, y;
    fin >> n >> x >> y;

    for (int i = 1; i <= n; ++ i) {
        fin >> p[ i ].first >> p[ i ].second;
    }

    long long ans = 0;
    for (int i = 1; i <= n; ++ i)
        v[ i ] = p[ i ].first;
    ans += solve( x );

    for (int i = 1; i <= n; ++ i)
        v[ i ] = p[ i ].second;
    ans += solve( y );

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}