Cod sursa(job #123330)

Utilizator alexeiIacob Radu alexei Data 15 ianuarie 2008 16:34:41
Problema Tribute Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 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];
using namespace std;
int main()
{
 
 ifstream f("tribute.in");
 ofstream g("tribute.out");
unsigned long long mint=inf,max=inf;
unsigned long long sol,sol1,sol2,temp;
 int n,val1,val2,pl1,pl2;
 f>>n>>pl1>>pl2;
     long long i,sum,min,poz1=0,poz2=0;
    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];
} 
    for(i=0; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<mint){
    mint=min;
    poz1=i;}
}
sol=0;temp=0;
if(pl1!=50000)
{
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(pl2!=50000){
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;}
 g<<temp<<"\n";
    //*/
    return 0;
}