Cod sursa(job #2135995)

Utilizator robx12lnLinca Robert robx12ln Data 19 februarie 2018 15:53:54
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int DIM = 100005;
int N, D[DIM];
pair<int,int> v[DIM];
inline int get_lower_bound( int x, int st, int dr ){
    while( st <= dr ){
        int mid = ( st + dr ) >> 1;
        if( v[mid].first <= x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return dr;
}
int main(){
    fin >> N;
    for( int i = 1; i <= N; i++ )
        fin >> v[i].second >> v[i].first;
    sort( v + 1, v + N + 1 );
    for( int i = 1; i <= N; i++ ){
        int pos = get_lower_bound( v[i].second, 1, i );
        D[i] = max( D[pos] + v[i].first - v[i].second, D[i] );
    }
    fout << D[N] << "\n";
    return 0;
}