Cod sursa(job #1724202)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 2 iulie 2016 15:16:16
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>
#define nmax 100050
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct interval
{
    int x, y;
};
interval a[nmax];
int n, b[nmax];
inline bool cmp(const interval A, const interval B)
{
    if(A.y == B.y) return A.x < B.x;
    return A.y < B.y;
}
int CB(int p)
{
    int st, dr, x, m, poz = 0;
    st = 1;
    dr = p - 1;
    x = a[p].x;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(a[m].y <= x)
        {
            poz = m;
            st = m + 1;
        }
        else dr = m - 1;
    }
    return poz;
}
int main()
{
    int i, poz;
    f >> n;
    for(i = 1; i <= n; i++)
        f >> a[i].x >> a[i].y;
    f.close();
    sort(a + 1, a + n + 1, cmp);
    for(i = 1; i <= n; i++)
    {
        b[i] = b[i - 1];
        poz = CB(i);
        b[i] = max(b[i],b[poz] + (a[i].y - a[i].x));
    }
    g << b[n] << "\n";
    g.close();
    return 0;
}