Pagini recente » Cod sursa (job #548864) | Cod sursa (job #1352040) | Cod sursa (job #2484064) | Cod sursa (job #2531714) | Cod sursa (job #1208082)
#include <fstream>
using namespace std;
int a[100001],b[100001];
int n,i,j;
long long best[100001],maxim[100001];
int pozitionare(int st,int dr)
{
int stng,drpt;
stng=0;
drpt=-1;
while (st<dr)
if (b[st]<b[dr])
{
st+=stng;
dr+=drpt;
}
else
{
swap(b[st],b[dr]);
swap(a[st],a[dr]);
stng=1-stng;
drpt=-1-drpt;
st+=stng;
dr+=drpt;
}
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()
{
ifstream f("heavymetlal.in");
ofstream g("heavymetal.out");
f>>n;
for (i=1;i<=n;++i)
f>>a[i]>>b[i];
quick(1,n);
best[1]=b[1]-a[1];
maxim[1]=best[1];
for (i=2;i<=n;++i)
{
cautbin(1,i-1);
best[i]=b[i]-a[i];
maxim[i]=maxim[i-1];
if (b[j]<=a[i])
best[i]+=maxim[j];
if (best[i]>maxim[i])
maxim[i]=best[i];
}
g<<maxim[n];
return 0;
}