Cod sursa(job #123122)

Utilizator alexeiIacob Radu alexei Data 14 ianuarie 2008 18:45:03
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<stdio.h>
#define nmax 50000
#define inf 2147483647
            
inline int mini(int a,int b)
{
       if(a<b)
       return a;
       return b;
}            

char q[nmax],w[nmax];
long long a[nmax],b[nmax];
long long mint=inf,max=inf;
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]='1';
     w[val2]='1';
     }
    
    sum=0; 
    for(i=0; i<=nmax; ++i)
{   a[i]=a[i-1]+sum;
      if(q[i]=='1')
      ++sum;
}
    sum=0;
    for(i=nmax; i>=0; --i)
{   b[i]=b[i+1]+sum;
      if(q[i]=='1')
      ++sum;
} 
    
    for(i=0; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<mint){
    mint=min;
    poz1=i;}
}
  
--pl1;
mint=mini(a[poz1-pl1]+b[poz1],a[poz1]+b[poz1+pl1]);

    sum=0; 
    for(i=0; i<=nmax; ++i)
{   a[i]=a[i-1]+sum;
      if(w[i]=='1')
      ++sum;
}
    sum=0;
    for(i=nmax; i>=0; --i)
{   b[i]=b[i+1]+sum;
      if(w[i]=='1')
      ++sum;
} 
    
    for(i=0; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<max){
    max=min;
    poz2=i;}
}
--pl2;
max=mini(a[poz2-pl2]+b[poz2],a[poz2]+b[poz2+pl2]);


 printf("%lld\n",mint+max);       
    
    
    return 0;
}