Cod sursa(job #1852619)

Utilizator mihaidanielmihai daniel mihaidaniel Data 20 ianuarie 2017 23:36:07
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#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;
}