Cod sursa(job #1867601)

Utilizator savigunFeleaga Dragos-George savigun Data 4 februarie 2017 11:12:23
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct con{
    int a, b;
} concert[100001];

int best[1000001];


int main()
{

    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");

    int n, tmax = 0;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        con c;
        cin >> c.a >> c.b;
        concert[i].a = c.a; concert[i].b = c.b;
        if (concert[i].b > tmax)
            tmax = concert[i].b;
    }

    //sort(concert + 1, concert + n + 1, compara);

    best[0] = 0;
    for (int i = 1; i <= tmax; ++i) {
        best[i] = best[i - 1];
        for (int j = 1; j <= n; ++j) {
            if (concert[j].b == i) {
                best[i] = max(best[i], best[concert[j].a] + (concert[j].b - concert[j].a));
            }
        }
    }

    cout << best[tmax];

    return 0;
}