Cod sursa(job #1848694)

Utilizator AndreiITCuriman Andrei AndreiIT Data 16 ianuarie 2017 15:23:12
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
/**
    code by purplecoder
*/
#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAX = 1e6 + 5;

int n, dp[MAX];

struct spect{
    int st, dr;
}v[MAX];

bool cmp(spect a, spect b){
    return a.dr < b. dr;
}

int main()
{
    cin>>n;
    for(int i=1; i<=n; ++i)
        cin>>v[i].st>>v[i].dr;
    sort(v + 1, v+n+1, cmp);
    for(int i=1; i<=n; ++i){
        dp[i] = dp[i-1];
        int st = 1, dr = i-1;
        while(st <= dr){
            int mij = (st + dr) / 2;
            if(v[mij].dr <= v[i].st)
                st = mij + 1;
            else
                dr = mij - 1;
        }
        if(dp[i] < v[i].dr - v[i].st + dp[dr])
            dp[i] = v[i].dr - v[i].st + dp[dr];
    }
    cout<<dp[n];
    return 0;
}