Cod sursa(job #1852651)

Utilizator mihaidanielmihai daniel mihaidaniel Data 21 ianuarie 2017 00:14:04
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#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;
}