Cod sursa(job #2546800)

Utilizator DordeDorde Matei Dorde Data 14 februarie 2020 15:57:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>

using namespace std;
int const NM = 1e5 + 1;
pair <int , int> v [NM] ;
int ans [NM] , dp [NM];
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
bool crt (pair <int , int> a , pair <int , int> b){
    return a . second < b . second;
}
int main (){
    int n;
    f >> n;
    for(int i = 1 ; i <= n ; ++ i)
        f >> v [i] . first >> v [i] . second;
    sort (v + 1 , v + 1 + n , crt);
    for(int i = 1 ; i <= n ; ++ i){
        int from , to;
        from = v [i] . first;
        to = v [i] . second;
        int pas = (1 << 16) , found = 0;
        while (pas){
            if (pas + found <= i && v [pas + found] . second <= from)
                found += pas;
            pas >>= 1;
        }
        dp [i] = to - from + ans [found];
        ans [i] = max (ans [i - 1] , dp [i]);
    }
    g << ans [n];
    return 0;
}