Cod sursa(job #2333609)

Utilizator borscalinCalin-Stefan Georgescu borscalin Data 1 februarie 2019 16:23:40
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#define NMAX 100000

using namespace std;

ifstream fin ( "heavymetal.in" );
ofstream fout ( "heavymetal.out" );

pair < int, int > A[1 + NMAX];

int n, ans, D[1 + NMAX];
int bs ( int val, int dr );

int main() {
    fin >> n;

    for ( int i = 1; i <= n; ++i )
        fin >> A[i].second >> A[i].first;
    sort ( A + 1, A + 1 + n );
    for ( int i = 1; i <= n; ++i ) {
        D[i] = A[i].first - A[i].second;
        D[i] = max ( D[i] + D[bs ( A[i].second, i - 1 )], D[i - 1] );
        ans = max ( ans, D[i] );
    }
    fout << ans;
}

int bs ( int val, int dr ) {

    int st = 1, mid, ans = 0;
    while ( st <= dr ) {
        mid = ( st + dr ) / 2;
        if ( A[mid].first > val )
            dr = mid - 1;
        else {
            ans = mid;
            st = mid + 1;
        }
    }
    return ans;
}