Cod sursa(job #1796845)

Utilizator ade_tomiEnache Adelina ade_tomi Data 3 noiembrie 2016 20:31:03
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100003
struct str 
{
    int x, y;
};
bool cmp (str a, str b)
{
    return a.y  < b.y;
}
using namespace std;
str v[NMAX];
int n, d[NMAX];
int main ()
{
    ifstream cin ("heavymetal.in");
    ofstream cout ("heavymetal.out");
    cin >> n;
    for (int i = 1; i <= n ;i++)
    {
        cin >> v[i].x >> v[i].y;
    }
    sort (v + 1, v + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
    {

        int l1 = 1;
        int sol = 0;
        int l2 = i - 1;
        while (l1 <= l2)
        {
            int mid = (l1 + l2) / 2;
            if (v[i].x < v[mid].y)
            {
                l2 = mid - 1;

            }
            else
            {
                l1 = mid + 1;
                sol = mid;
            }
        }
        d[i] = max (d[i - 1],  d[sol] + v[i].y - v[i].x);

    }
    cout << d[n];
    return 0;

}