Cod sursa(job #2289769)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 25 noiembrie 2018 11:33:59
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct costi
{
    int a, b;
}v[100005];

long long d[100005];

int prec(int x, int y, int val)
{
    int q = 0;
    while (x <= y)
    {
        int mij = (x + y) / 2;
        if (val < v[mij].b)
            y = mij - 1;
        else
        {
            x = mij + 1;
            q = mij;
        }
    }
    return q;
}

inline bool gicu (costi c, costi d)
{
    return c.b < d.b;
}

int main()
{
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> v[i].a >> v[i].b;
    sort(v + 1, v + n + 1, gicu);
    for (int i = 1; i <= n; i++)
        d[i] = max(d[i - 1], d[prec(1, i - 1, v[i].a)] + v[i].b - v[i].a);
    fout << d[n] << '\n';
    return 0;
}