Cod sursa(job #2136520)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 19 februarie 2018 22:45:56
Problema Heavy metal Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
//Pt emma
#include <iostream>
#include <fstream>
#include <algorithm>
#define DIM 100002
#define pr pair<int, int>
#define f first
#define s second

using namespace std;

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

int n, dp[DIM];

pr ev[DIM];

bool cmp(pr a, pr b){
    return a.s < b.s;
}

int main() {
    in>>n;
    for(int i = 1; i <= n; ++ i)
        in>>ev[i].f>>ev[i].s;
    sort(ev + 1, ev + n + 1, cmp);
    for(int i = 1; i <= n; ++ i){
        int st = 1;
        int dr = i - 1;
        while(st <= dr){
            int mid = (st + dr) / 2;
            if(ev[mid].s <= ev[i].f)
                st = mid + 1;
            else
                dr = mid - 1;
        }
        dp[i] = dp[dr] + ev[i].s - ev[i].f;
    }
    int maxim = -1;
    for(int i = 1; i <= n; ++ i)
        maxim = max(maxim, dp[i]);
    out<<maxim;
    return 0;
}