Cod sursa(job #1741230)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 13 august 2016 13:15:29
Problema Tribute Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include<bits/stdc++.h>
#define maxN 50005
#define INF INT_MAX
using namespace std;
pair<int,int> v[maxN];
long long best=LLONG_MAX,minim,minim1,s[maxN],d[maxN],s1[maxN],d1[maxN];
int imin,jmin;
int isx[maxN],isy[maxN],puncte[maxN],puncte2[maxN],xmax,ymax,n,dx,dy;
void generarex()
{
     if (isx[0]) puncte[0]=isx[0];
    for(int i=1;i<=xmax;i++)
        {
            puncte[i]=puncte[i-1]+isx[i];
        }
    s[0]=0;
    for(int i=1;i<=xmax;i++)
        s[i]=s[i-1]+1LL*puncte[i-1];
  /*  for(int i=0;i<=xmax;i++)
    {
        printf("%d ",s[i]);
    }*/
    if (isx[xmax]) puncte2[xmax]=isx[xmax];
    for(int i=xmax-1;i>=0;i--)
    {
        puncte2[i]=puncte2[i+1]+isx[i];
    }
    d[xmax]=0;
    for(int i=xmax-1;i>=0;i--)
    {
        d[i]=d[i+1]+1LL*puncte2[i+1];
    }
   /* printf("\n");
        for(int i=0;i<=xmax;i++)
    {
        printf("%d ",d[i]);
    }*/
}
void generarey()
{
    for(int i=0;i<=ymax;i++) puncte[i]=puncte2[i]=0;
    if (isy[0]) puncte[0]=isy[0];
    for(int i=1;i<=ymax;i++)
        {
            puncte[i]=puncte[i-1]+isy[i];
        }
    s1[0]=0;
    for(int i=1;i<=ymax;i++)
        s1[i]=s1[i-1]+1LL*puncte[i-1];
  /*  for(int i=0;i<=xmax;i++)
    {
        printf("%d ",s[i]);
    }*/
    if (isy[ymax]) puncte2[ymax]=isy[ymax];
    for(int i=ymax-1;i>=0;i--)
    {
        puncte2[i]=puncte2[i+1]+isy[i];
    }
    d1[ymax]=0;
    for(int i=ymax-1;i>=0;i--)
    {
        d1[i]=d1[i+1]+1LL*puncte2[i+1];
    }
}
void solve(int dx,int dy)
{
    minim=LLONG_MAX;
    for(int i=0;i<=(xmax-dx);i++)
    {
        if (1LL*(s[i]+d[i+dx])<minim)
        {
            minim=(s[i]+d[i+dx])*1LL;
            imin=i;
        }
    }
    minim1=LLONG_MAX;
    for(int i=0;i<=(ymax-dy);i++)
    {
        if (1LL*(s1[i]+d1[i+dy])<minim1)
        {
            minim1=(s1[i]+d1[i+dy])*1LL;
            jmin=i;
        }
    }
    if (((minim+minim1)*1LL)<best)
    {
        best=1LL*(minim+minim1);
    }
}
int main()
{
    freopen("tribute.in","r",stdin);
    freopen("tribute.out","w",stdout);
    scanf("%d%d%d",&n,&dx,&dy);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&v[i].first,&v[i].second);
        isx[v[i].first]++;
        isy[v[i].second]++;
        xmax=max(xmax,v[i].first);
        ymax=max(ymax,v[i].second);
    }
    generarex();
    generarey();
    solve(dx,dy);
   // if (dx!=dy) solve(dy,dx);
    printf("%lld\n",best);
    return 0;
}