Cod sursa(job #1692217)

Utilizator isav_costinVlad Costin Andrei isav_costin Data 20 aprilie 2016 14:52:26
Problema Heavy metal Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <algorithm>

struct date
{
    int st, dr;
} v[100005];
int d[100005], n;

using namespace std;

inline int maxim( int a, int b )
{
    if( a<b )
        a=b;
    return a;
}
inline int caut( int i )
{
    int st=1, dr=i, mid, last;
    while( st<dr )
    {
        mid=(st+dr)/2;
        if( v[mid].dr<=v[i].st )
        {
            st=mid+1;
            last=mid;
        }
        else
            dr=mid-1;
    }
    return last;
}
bool cmp( date a, date b )
{
    if( a.dr==b.dr )
        return a.st<b.st;
    return a.dr<b.dr;
}

int main()
{
    freopen( "heavymetal.in", "r", stdin );
    freopen( "heavymetal.out", "w", stdout );
    int m=0, i, j;
    scanf( "%d", &n );
    for( i=1;i<=n;i++ )
        scanf( "%d%d", &v[i].st, &v[i].dr );
    sort(v+1,v+n+1,cmp);
    for( i=1;i<=n;i++ )
    {
        j=caut(i);
        d[i]=maxim(d[i-1],d[j]+(v[i].dr-v[i].st));
        if( d[i]>m )
            m=d[i];
    }
    printf( "%d", m );
    return 0;
}