Cod sursa(job #2476617)

Utilizator Alex_AeleneiAlex Aelenei Ioan Alex_Aelenei Data 19 octombrie 2019 10:25:17
Problema Tribute Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <cstdio>
#include <algorithm>

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

    /**printf("\n");
    for(i=ll1;i<=ul1;++i)
        printf("%d %d\n",i,f1[i]);
    printf("\n");**/

    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("%d %d -> %d %d - %d %d\n",i,i+y1,nb,na,before,after);
    }
    printf("%d",ans1+ans2);
    return 0;
}