Cod sursa(job #123155)

Utilizator alexeiIacob Radu alexei Data 14 ianuarie 2008 20:47:00
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<stdio.h>
#define nmax 50000
#define inf 2147483647    

int q[nmax],w[nmax];
long long a[nmax+1],b[nmax+1],a1[nmax+1],b1[nmax+1];
long long mint=inf,max=inf;
long long sol,sol1,sol2,temp;
int main()
{
 freopen("tribute.in","r",stdin);
 freopen("tribute.out","w",stdout);
 
 int n,val1,val2,pl1,pl2;
 scanf("%d%d%d",&n,&pl1,&pl2);
    int i,sum,min,poz1=0,poz2=0;
    for(i=1; i<=n; i++)
   { scanf("%d%d",&val1,&val2);
    ++q[val1];
    ++w[val2];
     }
  sum=0; 
    for(i=0; i<=nmax; ++i)
{   a[i]=a[i-1]+sum;
      sum+=q[i];
}
    sum=0;
    for(i=nmax; i>=0; --i)
{   b[i]=b[i+1]+sum;
      sum+=q[i];
} 
    
    for(i=0; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<mint){
    mint=min;
    poz1=i;}
}

if(poz1-pl1>=0)
sol1=a[poz1-pl1]+b[poz1];
else
sol1=b[poz1];
if(poz1+pl1<=nmax)
sol2=b[poz1+pl1]+a[poz1];
else
sol2=a[poz1];

if(sol1<sol2)
sol+=sol1;
else
sol+=sol2;
temp=sol;
    sum=0; 
    for(i=0; i<=nmax; ++i)
{   a1[i]=a1[i-1]+sum; 
      sum+=w[i];
}
  b1[nmax+1]=0;
    sum=0;                 
  for(i=nmax; i>=0; --i)
{   b1[i]=b1[i+1]+sum;
      sum+=w[i]; 
}
    for(i=0; i<=nmax; ++i)
{   min=a1[i]+b1[i]; 
    if(min<max){
    max=min; 
    poz2=i;}
}

sol=0;
if(poz2-pl2>=0){
sol1=a1[poz2-pl2]+b1[poz2]; }
else
sol1=b1[poz2];
if(poz2+pl2<=nmax)
sol2=b1[poz2+pl2]+a1[poz2];
else
sol2=a1[poz2];
if(sol1<sol2)
sol+=sol1; 
else
sol+=sol2;;
temp+=sol;
 printf("%lld\n",temp);    
    
    return 0;
}