Cod sursa(job #1852655)

Utilizator mihaidanielmihai daniel mihaidaniel Data 21 ianuarie 2017 00:25:58
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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 maxim( int a, int b )
{
    return a > b ? a : b;
}

int main()
{
    freopen( "heavymetal.in", "r", stdin );
    freopen( "heavymetal.out", "w", stdout );

    int n, i, st, dr, mij, sol;
    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 = 1; i <= n; ++i )
    {
        st = 1;
        dr = i-1;
        sol = 0;
        while( st <= dr )
        {
            mij = (st + dr) / 2;
            if( dp[mij].f <= dp[i].s )
            {
                sol = mij;
                st = mij + 1;
            }
            else
                dr = mij - 1;
        }
        dp[i].t=maxim( dp[i-1].t, dp[i].t + dp[sol].t );
    }

    printf( "%d", dp[n].t );

    return 0;
}