Pagini recente » Cod sursa (job #2837883) | Cod sursa (job #777060) | Cod sursa (job #1807643) | Cod sursa (job #335396) | Cod sursa (job #2095233)
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
long long a[100001][2],dp[100001];
void Merge(long long l,long long r,long long m)
{
long long n1=m-l+1,n2=r-m,i,j=0,k=l;
long long L[n1][2],R[n2][2];
for(i=0;i<n1;i++)
{
L[i][0]=a[l+i][0];
L[i][1]=a[l+i][1];
}
for(i=0;i<n2;i++)
{
R[i][0]=a[m+i+1][0];
R[i][1]=a[m+i+1][1];
}
i=0;
while(i<n1&&j<n2)
{
if(L[i][1]<R[j][1])
{
a[k][0]=L[i][0];
a[k][1]=L[i][1];
i++;
}
else
{
a[k][0]=R[j][0];
a[k][1]=R[j][1];
j++;
}
k++;
}
while(i<n1)
{
a[k][0]=L[i][0];
a[k][1]=L[i][1];
i++;
k++;
}
while(j<n2)
{
a[k][0]=R[j][0];
a[k][1]=R[j][1];
j++;
k++;
}
}
void mergesort(long long l,long long r)
{
if(r>l)
{
long long m=(l+r)/2;
mergesort(l,m);
mergesort(m+1,r);
Merge(l,r,m);
}
}
int main()
{
long long n,i,j=1;
in>>n;
for(i=1;i<=n;i++)
in>>a[i][0]>>a[i][1];
mergesort(1,n);
for(i=1;i<=a[n][1];i++)
{
dp[i]=dp[i-1];
while(a[j][1]==i)
{
dp[i]=max(dp[i],dp[a[j][0]]+a[j][1]-a[j][0]);
j++;
}
}
out<<dp[a[n][1]];
return 0;
}