Cod sursa(job #2208183)

Utilizator giotoPopescu Ioan gioto Data 28 mai 2018 16:03:21
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;

int n, dx, dy;
int fx[50005], fy[50005];
int main()
{
    freopen("tribute.in", "r", stdin);
    freopen("tribute.out", "w", stdout);

    scanf("%d%d%d", &n, &dx, &dy);
    int x, y;
    for(int i = 1; i <= n ; ++i){
        scanf("%d%d", &x, &y);
        ++fx[x]; ++fy[y];
    }

    long long solx = 1000000000000000000, nrd = 0, nrs = 0, ss = 0, sd = 0;
    for(int i = dx; i <= 50000 ; ++i){
        nrd += fx[i];
        sd = sd + fx[i] * i;
    }
    for(int i = 0; i <= 50000 ; ++i){
        if(i - 1 >= 0){
            nrs += fx[i - 1];
            ss = ss + fx[i - 1] * (i - 1);
        }
        if(i + dx <= 50000){
            nrd -= fx[i + dx];
            sd = sd - fx[i + dx] * (i + dx);
        }
        solx = min(solx, 1LL * nrs * i - ss + sd - 1LL * nrd * (i + dx));
    }

    long long soly = 1000000000000000000; nrd = 0, nrs = 0, ss = 0, sd = 0;
    for(int i = dy; i <= 50000 ; ++i){
        nrd += fy[i];
        sd = sd + fy[i] * i;
    }
    for(int i = 0; i <= 50000 ; ++i){
        if(i - 1 >= 0){
            nrs += fy[i - 1];
            ss = ss + fy[i - 1] * (i - 1);
        }
        if(i + dy <= 50000){
            nrd -= fy[i + dy];
            sd = sd - fy[i + dy] * (i + dy);
        }
        soly = min(soly, 1LL * nrs * i - ss + sd - 1LL * nrd * (i + dy));
    }

    printf("%lld", solx + soly);
    return 0;
}