Pagini recente » Cod sursa (job #1798247) | Cod sursa (job #2732025) | Cod sursa (job #3192904) | Cod sursa (job #181532) | Cod sursa (job #2106325)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("heavymetal.in");
ofstream cout("heavymetal.out");
const int N=100005;
const int L=30;
struct spectacol
{
int start, stop;
} v[N];
int n, sfarsit[N], m, dp[N];
bool cmp(spectacol x, spectacol y)
{
return x.stop < y.stop;
}
int caut(int x)
{
int r=0,pas=1<<L;
while(pas!=0)
{
if(r+pas<=m && sfarsit[r+pas]<=x)
r+=pas;
pas/=2;
}
return r;
}
void citire()
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>v[i].start>>v[i].stop;
}
void sortare()
{
/*
for(int i=1; i<n; i++)
for(int j=i+1; j<=n; j++)
if(v[i].stop>v[j].stop)
swap(v[i], v[j]);
*/
sort(v + 1, v + n + 1, cmp);
}
void solve()
{
int i, j, dr, st;
sfarsit[1]=v[1].stop;
for(i=2, j=1; i<=n; i++)
{
if(v[i].stop != v[i-1].stop)
sfarsit[++j] = v[i].stop;
}
m=j;
//for(i=1; i<=m; i++)
//cout<<sfarsit[i]<<' ';
for(i=1; i<=n; i++)
{
st=caut(v[i].start);
dr=caut(v[i].stop);
dp[dr]=max(dp[dr], dp[st]+v[i].stop-v[i].start);
dp[dr]=max(dp[dr], dp[dr-1]);
//cout<<dp[i]<<' ';
}
cout<<dp[m];
}
int main()
{
citire();
sortare();
solve();
return 0;
}