Pagini recente » Cod sursa (job #661820) | Cod sursa (job #1695560) | Cod sursa (job #2449284) | Cod sursa (job #1190561) | Cod sursa (job #1852651)
#include <cstdio>
#include <vector>
using namespace std;
struct interval
{
int t, f;
} a;
vector <interval> dp[100010];
int maxim( int a, int b );
void af( int n );
int main()
{
freopen( "heavymetal.in", "r", stdin );
freopen( "heavymetal.out", "w", stdout );
int n, i, j, s, f, ma = 0;
scanf( "%d", &n );
for( i = 0; i < n; ++i )
{
scanf( "%d%d", &s, &f );
a.f = f;
a.t = f - s;
dp[s].push_back( a );
if( s > ma )
{
ma = s;
}
}
n = ma;
for( i = n; i >= 0; --i )
{
//af( n );
if( dp[i].empty() )
{
dp[i].push_back( dp[i+1][0] );
continue;
}
for( j = 0; j < dp[i].size(); ++j )
{
if( dp[i][j].f <= n )
{
dp[i][0].t = maxim( dp[i][0].t, dp[i][j].t + dp[ dp[i][j].f ][0].t );
}
}
}
//af( n );
printf( "%d", dp[0][0].t );
return 0;
}
void af( int n )
{
int i, j;
for( i = 0; i <= n; ++i )
{
printf( "\n%d:", i );
for( j = 0; j < dp[i].size(); ++j )
{
printf( " %d", dp[i][j] );
}
}
printf("\n\n");
}
int maxim( int a, int b )
{
return a > b ? a : b;
}