Pagini recente » Cod sursa (job #1217205) | Cod sursa (job #242767) | Cod sursa (job #2851875) | Cod sursa (job #1438557) | Cod sursa (job #1852619)
#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 main()
{
freopen( "heavymetal.in", "r", stdin );
freopen( "heavymetal.out", "w", stdout );
int n, i, j, tm = 0, ma;
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=0; i < n; ++i )
{
printf( "%d %d\n", dp[i].s, dp[i].f );
}
for( i=0; i < n; ++i )
{
printf( "%d ", dp[i].t );
}
printf("\n");//*/
for( i = n; i > 0; --i )
{
ma = 0;
for( j = i + 1; j <= n && ma == 0; ++j )
{
if( dp[i].f <= dp[j].s )
{
ma = j;
}
}
dp[i].t += dp[ma].t;
if( dp[i].t > tm )
{
tm = dp[i].t;
}
/*
for( j=0; j < n; ++j )
{
printf( "%d ", dp[j].t );
}
printf("\n");//*/
}
printf( "%d", tm );
return 0;
}