Cod sursa(job #2289654)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 24 noiembrie 2018 23:10:52
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>

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 p)
{
    while (x <= y)
    {
        int mij = (x + y) / 2;
        if (v[p].a < v[mij].b)
        {
            y = mij - 1;
            if (v[mij - 1].b < v[p].a)
                return mij - 1;
        }
        if (v[p].a == v[mij].b)
            return mij;
        if (v[p].a > v[mij].b)
        {
            x = mij + 1;
            if (v[mij + 1].b > v[p].a)
                return mij + 1;
        }
    }
}

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