Cod sursa(job #1221657)

Utilizator xtreme77Patrick Sava xtreme77 Data 21 august 2014 05:13:01
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <algorithm>

const char IN [ ] = "heavymetal.in" ;
const char OUT [ ] = "heavymetal.out" ;
const int MAX = 100014 ;

using namespace std;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

struct hm {
    int x , y ;
};

hm q [ MAX ] ;

bool cmp ( hm a , hm b )
{
    return a.y < b.y ;
}

int din [ MAX ] ;

int caut ( int st , int dr , int val )
{
    int last = -1 ;
    while ( st <= dr )
    {
        int mij = ( st + dr ) >> 1 ;
        if ( q [ mij ].y <= val )
        {
            last = mij ;
            st = mij + 1 ;
        }
        else dr = mij - 1 ;
    }
    return last ;
}

int main( )
{
    int n ;
    fin >> n ;
    for ( int i = 1 ; i <= n ; ++ i )
        fin >> q [ i ].x >> q [ i ].y ;
    sort ( q + 1 , q + n + 1 , cmp ) ;
    din [ 1 ] = q [ 1 ].y - q [ 1 ].x ;
    for ( int i = 2 ; i <= n ; ++ i )
    {
        int poz = caut ( 1 , i - 1 , q [ i ].x ) ;
        din [ i ] = din [ i - 1 ];
        if ( poz == - 1 )
            din [ i ] = max ( din [ i ] , q [ i ].y - q [ i ].x ) ;
        else din [ i ] = max ( din [ i ] , din [ poz ] + q [ i ].y - q [ i ].x ) ;
    }
    fout << din [ n ] ;
    return 0;
}