Pagini recente » Cod sursa (job #2974163) | Cod sursa (job #1429736) | Cod sursa (job #902602) | Cod sursa (job #129765) | Cod sursa (job #1852655)
#include <cstdio>
#include <algorithm>
using namespace std;
struct interval
{
int s, f, t;
} dp[100010];
bool cmp( interval a, interval b )
{
return a.f != b.f ? a.f < b.f : a.s < b.s;
}
int maxim( int a, int b )
{
return a > b ? a : b;
}
int main()
{
freopen( "heavymetal.in", "r", stdin );
freopen( "heavymetal.out", "w", stdout );
int n, i, st, dr, mij, sol;
scanf( "%d", &n );
for( i = 0; i < n; ++i )
{
scanf( "%d%d", & dp[i].s, & dp[i].f );
dp[i].t = dp[i].f - dp[i].s;
}
sort( dp, dp + n, cmp );
for( i = 1; i <= n; ++i )
{
st = 1;
dr = i-1;
sol = 0;
while( st <= dr )
{
mij = (st + dr) / 2;
if( dp[mij].f <= dp[i].s )
{
sol = mij;
st = mij + 1;
}
else
dr = mij - 1;
}
dp[i].t=maxim( dp[i-1].t, dp[i].t + dp[sol].t );
}
printf( "%d", dp[n].t );
return 0;
}