Cod sursa(job #2644119)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 23 august 2020 15:28:12
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
#define NMAX 50005
#define ll long long
using namespace std;

int n, dx, dy, x[NMAX], y[NMAX];

ll get(int pos, int x[], int dx){
    ll ans = 0;
    for (int i=1;i<=n;i++){
        if(pos <= x[i] && x[i] <= pos + dx) continue;
        ans += min(abs(pos - x[i]), abs(pos + dx - x[i]));
    }
    return ans;
}

ll solve(int x[], int dx){
    int st = 0, dr = 50000;

    while (st < dr - 2){
        int mid1 = (st + st + dr) / 3;
        int mid2 = (st + dr + dr) / 3;

        ll ans1 = get(mid1, x, dx);
        ll ans2 = get(mid2, x, dx);

        if (ans1 < ans2) dr = mid2;
        else st = mid1;
    }


//    cout << st << ' ' << get(st, x, dx) << ' ' << get(st+1, x, dx) << ' ' << get(st+2, x, dx) << '\n';
    return min({get(st, x, dx), get(st+1, x, dx), get(st+2, x, dx)});
}

int main()
{
    cin.sync_with_stdio(false);
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);

    cin >> n >> dx >> dy;
    for (int i=1;i<=n;i++){
        cin >> x[i] >> y[i];
    }

    ll ans = solve(x, dx) + solve(y, dy);

    cout << ans << '\n';
    return 0;
}