Cod sursa(job #1726936)

Utilizator SaitamaSaitama-san Saitama Data 9 iulie 2016 15:24:58
Problema Heavy metal Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int n, sol[100000];

struct timp
{
    int x, y;
};

timp v[100000];

inline bool cmp(const timp A, const timp B)
{
    if(A.y == B.y) return A.x < B.x;
    return A.y < B.y;
}

void Read()
{
    int i;
    fin >> n;
    for(i = 1; i <= n; i++)
        fin >> v[i].x >> v[i].y;
    fin.close();
}

int CB(int p)
{
    int st, dr, x, m, poz;
    st = 1;
    dr = p - 1;
    x = v[p].x;
    poz = 0;
    while(st <= dr)
    {
        m = (st + dr) / 2;
        if(v[m].y <= x)
        {
            poz = m;
            st = m + 1;
        }
        else dr = m - 1;
    }
    return poz;
}

inline void Solve()
{
    int i;
    sort(v + 1, v + 1 + n, cmp);
    for(i = 1; i <= n; i++)
        sol[i] = max(sol[i - 1], sol[CB(i)] + (v[i].y - v[i].x));
    fout << sol[n] << "\n";
    fout.close();
}

int main()
{
    Read();
    Solve();
    return 0;
}