Cod sursa(job #1726931)

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

using namespace std;

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

int n, sol[100000];
pair <int, int> v[100000];

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

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

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

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