Cod sursa(job #2721450)

Utilizator Iulia14iulia slanina Iulia14 Data 11 martie 2021 20:11:50
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("tribute.in");
ofstream cout ("tribute.out");
#define ll long long
const ll nmax = 50005;
ll x[nmax];
ll sx[nmax];
ll y[nmax];
ll sy[nmax];
ll n;
ll best(ll x[], ll sx[], ll dx)
{
    ll xx, p, st = 0, dr = 0;
    ll ans = 2e16;
    for (p = 0; p <= nmax - 5; p++)
    {
        while (x[st + 1] <= p && st <= n)
            st++;
        while (x[dr + 1] <= p + dx && dr < n)
            dr++;
        ll lft = p * st - sx[st];
        ll rgt = sx[n] - sx[dr] - (p + dx) * (n - dr);
        if (ans > lft + rgt)
        {
            ans = lft + rgt;
            xx = p;
        }
    }
    return ans;
}
int main()
{
    ll dx, dy, i;
    cin >> n >> dx >> dy;
    for (i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    sort(x + 1, x + n + 1);
    for (i = 1; i <= n; i++)
        sx[i] = sx[i - 1] + x[i];
    sort(y + 1, y + n + 1);
    for (i = 1; i <= n; i++)
        sy[i] = sy[i - 1] + y[i];
    cout << best(x, sx, dx) + best(y, sy, dy);
    return 0;
}