Pagini recente » Cod sursa (job #573868) | Cod sursa (job #2979940) | Cod sursa (job #5887) | Profil florinhaja | Cod sursa (job #2397943)
#include <bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define maxn 100000
//#define aaa system("pause");
using namespace std;
pii v[maxn+5];
pii dp[maxn+5]; ///dp[i]-timp maxim cu bandele 0..i (fi) capat dreapta (se)
bool cmp ( pii a, pii b )
{
if ( a.se != b.se ) return a.se < b.se;
return a.fi < b.fi;
}
int main ()
{
ifstream fin ( "heavymetal.in" );
ofstream fout ( "heavymetal.out" );
int n; fin >> n;
int i, j, z, itv, _M = 0, pas;
for ( i = 0; i < n; i++ ) fin >> v[i].fi >> v[i].se;
sort ( v, v + n, cmp );
for ( i = 0; i < n; i++ )
{
itv = v[i].se-v[i].fi;
dp[i] = {itv,v[i].se};
for ( j = 0, pas = (1<<20); pas > 0; pas /= 2 )
if ( j + pas < i && dp[j+pas].se <= v[i].fi && dp[i].fi < dp[j+pas].fi + itv ) j += pas;
if ( dp[j].fi > 0 ) dp[i] = {dp[j].fi + itv - (dp[j].se==v[i].fi),v[i].se};
_M = max(_M, dp[i].fi);
}
fout << _M;
fin.close ();
fout.close ();
return 0;
}