Pagini recente » Cod sursa (job #1646134) | Cod sursa (job #672950) | Cod sursa (job #736460) | Cod sursa (job #1885640) | Cod sursa (job #664755)
Cod sursa(job #664755)
#include <fstream>
using namespace std;
int a[100001],b[100001];
int n,i,j;
int best[100001];
int pozitionare(int st,int dr)
{
int xst,xdr;
xst=0;
xdr=-1;
while (st<dr)
if (b[st]<b[dr])
{
st+=xst;
dr+=xdr;
}
else
{
swap(b[st],b[dr]);
swap(a[st],a[dr]);
xst=1-xst;
xdr=-1-xdr;
st+=xst;
dr+=xdr;
}
return st;
}
void cautbin(int st,int dr)
{
int mij=(st+dr)/2;
if (st!=dr)
{
if (b[mij]>a[i])
cautbin(st,mij-1);
else
if (b[mij+1]<=a[i])
cautbin(mij+1,dr);
else
cautbin(mij,mij);
}
else
j=st;
}
void quick(int st,int dr)
{
int p=pozitionare(st,dr);
if (st<p-1)
quick(st,p-1);
if (p+1<dr)
quick(p+1,dr);
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
scanf("%d%d",&a[i],&b[i]);
quick(1,n);
best[1]=b[1]-a[1];
for (i=2;i<=n;++i)
{
cautbin(1,i-1);
best[i]=b[i]-a[i];
if (b[j]<=a[i])
best[i]+=best[j];
}
printf("%d\n",best[n]);
return 0;
}