Cod sursa(job #2662446)

Utilizator andu2006Alexandru Gheorghies andu2006 Data 24 octombrie 2020 09:27:15
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda long-contest-bd-1 Marime 1.25 kb
#include <bits/stdc++.h>
#define NMAX 100003

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ifstream fin("tribute.in");
ofstream fout("tribute.out");
ll x[NMAX],y[NMAX];
ll sumx[NMAX],sumy[NMAX];
template<char c>
ll getSum(ll a, ll b){
    if(b<a) return 0;
    if(c=='x')
        return sumx[b]-(a?sumx[a-1]:0);
    else
        return sumy[b]-(a?sumy[a-1]:0);
}
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,dx,dy,ansx=1e10,ansy=1e10;
    fin>>n>>dx>>dy;
    for(ll i=0;i<n;i++)
        fin>>x[i]>>y[i];
    sort(x,x+n),sort(y,y+n);
    for(ll i=0;i<n;i++){
        sumx[i]=(i?sumx[i-1]:0)+x[i];
        sumy[i]=(i?sumy[i-1]:0)+y[i];
    }
    for(ll i=0;i<NMAX;i++){
        ll cntLess=lower_bound(x,x+n,i)-x,cntGreater=x+n-upper_bound(x,x+n,i+dx);
        ll num1=i*cntLess-getSum<'x'>(0,cntLess-1);
        ll num2=getSum<'x'>(n-cntGreater,n-1)-(i+dx)*cntGreater;
        ansx=min(ansx,num1+num2);

        cntLess=lower_bound(y,y+n,i)-y,cntGreater=y+n-upper_bound(y,y+n,i+dy);
        num1=i*cntLess-getSum<'y'>(0,cntLess-1);
        num2=getSum<'y'>(n-cntGreater,n-1)-(i+dy)*cntGreater;
        ansy=min(ansy,num1+num2);
    }
    fout<<ansx+ansy;
	return 0;
}