Cod sursa(job #1689340)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 14 aprilie 2016 10:12:43
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

const int Nmax = 100005;
int n, DP[Nmax];
pair <int, int> P[Nmax];

bool Crit(pair <int, int> a, pair <int, int> b)
{
    return a.second<b.second;
}

int main()
{
    f>>n;
    for(int i = 1; i <= n; i++)
    {
        f>>P[i].first>>P[i].second;
    }
    sort(P+1, P+1+n, Crit);
    for(int i = 1; i <= n; i++)
    {
        int li = 1, ls = i-1, pos = 0;
        while(li <= ls)
        {
            int mid = (li+ls)/2;
            if(P[mid].second <= P[i].first)
            {
                pos = mid;
                li = mid+1;
            }
            else ls = mid-1;
        }
        DP[i] = max(DP[i-1], DP[pos]+P[i].second-P[i].first);
    }
    g<<DP[n]<<'\n';
    return 0;
}