Cod sursa(job #2227851)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 2 august 2018 00:24:19
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
 
const int Dim = 100001;
pair < int, int > A[Dim];
 
int n,ma,D[Dim];
int CB(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[CB(A[i].second,i-1)],D[i-1]);
        ma = max(ma,D[i]);
    }
    fout << ma;   
}
 
int CB(int val, int dr) {
     
    int st = 1,mj,sol = 0;
    while ( st <= dr ){ 
        mj = ( st + dr )/2;
        if ( A[mj].first > val) 
            dr = mj - 1;
        else {
            sol = mj;
            st = mj + 1;
            }
    }
    return sol;
}