Cod sursa(job #2167458)

Utilizator Y0da1NUME JMECHER Y0da1 Data 13 martie 2018 21:49:07
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define maxn 100005
using namespace std;
struct interval{
    int st, dr;
    bool operator < (const interval & a) const
    {
        if (dr == a.dr)
            return st <= a.st;
        return dr <= a.dr;

    }
};

interval v[maxn];
int d[maxn];
int N;

int main()
{
    ifstream in ("heavymetal.in");
    ofstream out ("heavymetal.out");

    in>>N;
    for(int i = 1; i <= N; ++i)
    {
        in>>v[i].st;
        in>>v[i].dr;
    }

    sort(v + 1, v + N + 1);
    d[1] = v[1].dr - v[1].st;

    for(int i = 2; i <= N; ++i)
    {
        int lo = 1, hi = i - 1, mid;
        while(lo <= hi)
        {
            mid = (lo + hi)/2;
            if(v[mid].dr <= v[i].st)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        d[i] = max(v[i].dr - v[i].st + d[hi], d[i-1]);
    }
    out<<d[N];
    return 0;
}