Pagini recente » Cod sursa (job #1349665) | Cod sursa (job #3214180) | Cod sursa (job #915678) | Cod sursa (job #2663287) | Cod sursa (job #2104177)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,i,j,dp[100005],mx[100005],rz;
int st,dr,mid,cb;
struct interv
{ int a, b;} v[100005];
bool comp(interv A,interv B)
{
if(A.a==B.a) return A.b>B.b;
return A.a>B.a;
}
int main () {
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].a>>v[i].b;
sort(v+1,v+n+1,comp);
dp[1]=v[1].b-v[1].a;
mx[1]=v[1].a;
rz=dp[1];
for(i=2;i<=n;i++)
{
st=1; dr=i-1;
while(st<=dr)
{
mid=st+(dr-st)/2;
if(mx[mid]>=v[i].b) st=mid+1;
if(mx[mid]<v[i].b) dr=mid-1;
}
while(mx[mid]<v[i].b&&mid>0) mid--;
while(mx[mid+1]>=v[i].b&&mid<i-1) mid++;
if(dp[mid]+v[i].b-v[i].a>dp[i-1])
{
dp[i]=dp[mid]+v[i].b-v[i].a;
mx[i]=v[i].a;
}
else
{
dp[i]=dp[i-1];
mx[i]=mx[i-1];
}
}
fout<<dp[n]<<"\n";
}