Cod sursa(job #2289759)

Utilizator IoanaDraganescuIoana Draganescu IoanaDraganescu Data 25 noiembrie 2018 11:20:30
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 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 val)
{
    int q = 0;
    while (x <= y)
    {
        int mij = (x + y) / 2;
        if (val <= v[mij].b)
        {
            q = d[mij];
            y = mij - 1;
        }
        if (val > v[mij].b)
            x = mij + 1;
    }
    return q;
}

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);
            }
    for (int i = 1; i <= n; i++)
        d[i] = max(d[i - 1], prec(1, i - 1, v[i].a) + v[i].b - v[i].a);
    fout << d[n] << '\n';
    return 0;
}