Cod sursa(job #1708858)

Utilizator valentinoMoldovan Rares valentino Data 28 mai 2016 00:46:27
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <algorithm>
#include <fstream>
#define N 100010

using namespace std;

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

struct z
{
    int x,y;
}v[N];
int n, sol[N], maxx;

bool cmp(z a, z b)
{
    return a.x < b.x;
}

int binsearch(int st, int dr, int val)
{
    int poz, mid;
    while(st <= dr)
    {
        mid = (st + dr)/2;
        if(v[mid].y <= val) st = mid + 1, poz = mid;
        else dr = mid - 1;
    }
    return st-1;

}

int main()
{
    int res = 0;
    f >> n;
    for(int i = 1; i <= n; ++i)
    {
        sol[i] = -1;
        f >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmp);
    sol[0] = 0;
    for(int i = 1; i <= n; ++i)
    {
        int last = binsearch(0, i - 1, v[i].x);
        sol[i] = max(sol[i-1], sol[last] + v[i].y - v[i].x);
        res = max(res, sol[i]);
    }
    g << res << '\n';
    return 0;
}