Pagini recente » Cod sursa (job #1274556) | Cod sursa (job #267580) | Cod sursa (job #231785) | Cod sursa (job #2839979) | Cod sursa (job #123359)
Cod sursa(job #123359)
#include<fstream>
#define nmax 50000
#define inf 4294967295
int q[nmax+1],w[nmax+1];
long long a[nmax+1],b[nmax+1],a1[nmax+1],b1[nmax+1];
long long sum;
int n,val1,val2,pl1,pl2;
long long val;
using namespace std;
int main()
{
long long sol=0,sol1,sol2,temp;
ifstream f("tribute.in");
ofstream g("tribute.out");
f>>n>>pl1>>pl2;
int i,poz1,poz2;
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];
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;
}