Cod sursa(job #1852656)

Utilizator mihaidanielmihai daniel mihaidaniel Data 21 ianuarie 2017 00:39:40
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <cstdio>
#include <vector>

using namespace std;

int l[100010];
vector <int> 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 );
        dp[f].push_back( s );
        ma = maxim( ma, f );
    }

    n = ma;

    for( i = 1; i <= n; ++i )
    {
        l[i] = l[i - 1];
        for( j = 0; j < dp[i].size(); ++j )
        {
            l[i] = maxim( l[i] ,l[ dp[i][j] ] + i - dp[i][j] );
        }
    }

    printf( "%d", l[n] );

    return 0;
}

int maxim( int a, int b )
{
    return a > b ? a : b;
}