Cod sursa(job #2637170)

Utilizator cyg_vladioanBirsan Vlad cyg_vladioan Data 21 iulie 2020 16:42:07
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int DMAX = 50001;
const int INF = 2.e9;
int fx[DMAX + 5] , fy[DMAX + 5];
int calculeaza(int f[DMAX + 5] , int d)
{
    int i , s , nr , minim;
    int d1[DMAX + 5] , d2[DMAX + 5];
    memset(d1 , 0 , sizeof(d1));
    memset(d2 , 0 , sizeof(d2));
    s = nr = 0;
    for(i = DMAX ; i >= 0 ; i --)
    {
        nr += f[i];
        s += nr;
    }
    for(i = 0 ; i <= DMAX ; i ++)
    {
        s -= nr;
        nr -= f[i];
        d1[i] = s;
    }
    nr = s = 0;
    for(i = 1 ; i <= DMAX ; i ++)
    {
        nr += f[i];
        s += nr;
    }
    for(i = DMAX ; i >= 1 ; i --)
    {
        s -= nr;
        nr -= f[i];
        d2[i] = s;
    }
    minim = INF;
    for(i = d ; i <= DMAX ; i ++)
        minim = min(minim , d1[i] + d2[i - d]);
    return minim;
}
int main()
{
    freopen("tribute.in" , "r" , stdin);
    freopen("tribute.out" , "w" , stdout);
    int n , x , y , dx , dy , i;
    scanf("%d%d%d" , &n , &dx , &dy);
    for(i = 1 ; i <= n ; i ++)
    {
        scanf("%d%d" , &x , &y);
        fx[x + 1] ++;
        fy[y + 1] ++;
    }
    printf("%d\n" , calculeaza(fx , dx) + calculeaza(fy , dy));
    return 0;
}