Cod sursa(job #2457448)

Utilizator CharacterMeCharacter Me CharacterMe Data 17 septembrie 2019 19:55:06
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>
typedef long long ll;
ll n, dx, dy, i, j, k, mx, my;
ll cntX[50001], cntY[50001];
void read();
ll solve(ll list[], ll dx, ll mx);
void write();
int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);
    read();
    write();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
void read(){
    scanf("%lld%lld%lld", &n, &dx, &dy);
    for(i=1; i<=n; ++i){
        ll x, y;
        scanf("%lld%lld", &x, &y);
        ++cntX[x]; ++cntY[y];
        mx=std::max(mx, x);
        my=std::max(my, y);
    }
}
ll solve(ll list[], ll dx, ll mx){
    if(mx<=dx) return 0LL;
    ll d=0, l=0, r=0, ret;
    for(i=dx+1; i<=mx; ++i){
        r+=list[i]; d+=list[i]*(i-dx);
    }
    ret=d;
    for(i=dx+1; i<=mx; ++i){
        l+=list[i-dx-1]; d+=l;
        d-=r; r-=list[i];
        ret=std::min(ret, d);
    }
    return ret;
}
void write(){
    printf("%lld", solve(cntX, dx, mx)+solve(cntY, dy, my));
}