Cod sursa(job #2531852)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 26 ianuarie 2020 20:07:10
Problema Tribute Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <algorithm>

using namespace std;
const int NMAX=5*1e4;
long long f1[NMAX+5],f2[NMAX+5];
int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    long long n,x1,y1,x,y,i,ans1=NMAX,ans2=NMAX;
    long long nr1,nr2,ul1=0,ll1=NMAX,ul2=0,ll2=NMAX;
    long long before,after,na,nb;
    scanf("%lld%lld%lld",&n,&x1,&y1);
    for(i=1;i<=n;++i)
    {
        scanf("%lld%lld",&x,&y);
        ++f1[x];++f2[y];
        ll1=min(ll1,x);ul1=max(ul1,x);
        ll2=min(ll2,y);ul2=max(ul2,y);
    }
    before=0;nb=0;after=0;na=0;
    for(i=ll1+x1+1;i<=ul1;++i)
        after+=f1[i]*(i-(ll1+x1)),na+=f1[i];
    for(i=ll1+1;i<=ul1-x1;++i)
    {
        ans1=min(ans1,after+before);
        after-=na;
        na-=f1[i+x1];
        nb+=f1[i-1];
        before+=nb;
        ans1=min(ans1,after+before);
    }

    before=0;nb=0;after=0;na=0;
    for(i=ll2+y1+1;i<=ul2;++i)
        after+=f2[i]*(i-(ll2+y1)),na+=f2[i];
    for(i=ll2+1;i<=ul2-y1;++i)
    {
        ans2=min(ans2,after+before);
        after-=na;
        na-=f2[i+y1];
        nb+=f2[i-1];
        before+=nb;
        ans2=min(ans2,after+before);
    }
    printf("%lld",ans1+ans2);
    return 0;
}