Cod sursa(job #123364)

Utilizator alexeiIacob Radu alexei Data 15 ianuarie 2008 17:54:02
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#define nmax 50000
#define inf 4294967295
int q[nmax+1],w[nmax+1];
unsigned long long a[nmax+1],b[nmax+1],a1[nmax+1],b1[nmax+1];
long long sum;
unsigned int n,val1,val2,pl1,pl2; 
long long val;     
using namespace std;
int main()
{ 
unsigned long long sol=0,sol1,sol2,temp;

 ifstream f("tribute.in");
 ofstream g("tribute.out");

 f>>n>>pl1>>pl2;
   int i,poz1,poz2;
 unsigned long long min;
    for(i=1; i<=n; i++)
   { f>>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];
} 
val=a[0]+b[0];
poz1=0; 
    for(i=1; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<val){
    val=min;
    poz1=i;}
}

sol1=inf;
if(pl1!=50000)
{
for(i=0; i<=pl1&&poz1+i<=nmax; ++i)
{ if(poz1-pl1+i>=0)
  {temp=a[poz1-pl1+i]+b[poz1+i];
   if(temp<sol1)
   sol1=temp;
  }
}
//g<<sol1<<"\n";
}
else
sol1=0;

sol+=sol1;
//g<<"sol "<<sol<<"\n";
    sum=0; 
    for(i=0; i<=nmax; ++i)
{   a1[i]=a1[i-1]+sum; 
      sum+=w[i];
}
    sum=0;                 
  for(i=nmax; i>=0; --i)
{   b1[i]=b1[i+1]+sum; 
      sum+=w[i]; 
}
val=a1[0]+b1[0];
poz2=0;
    for(i=0; i<=nmax; ++i)
{   min=a1[i]+b1[i]; 
    if(min<val){
    val=min; 
    poz2=i;}
}

sol2=inf;
if(pl2!=50000)
{
for(i=0; i<=pl2&&poz2+i<=nmax; ++i)
{ if(poz2-pl2+i>=0)
  {temp=a1[poz2-pl2+i]+b1[poz2+i];
   if(temp<sol2)
   sol2=temp;
  }
}

}
else
sol2=0;
sol+=sol2; 
g<<sol<<"\n";
  
//*/
  return 0;
}