Cod sursa(job #1430514)

Utilizator alexandru.jercaianuJercaianu Alexandru alexandru.jercaianu Data 8 mai 2015 15:57:59
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

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

int N;
int a[100002], b[100002], d[100000];

int main() 
{
    fin >> N;
    int m = 0;
    for (int i = 0; i < N; i++) {
        int x, y;
        fin >> x >> y;
        a[i] = x;
        b[i] = y;
        if (y > m)
            m = y;
    }

    for (int i = 1; i <= m; i++) {
        d[i] = d[i - 1];
        for (int j = 0; j < N; j++) {
            if (b[j] == i) {
                d[i] = max(d[i], d[a[j]] + b[j] - a[j]);
            }
        }
    }
    fout << d[m] << endl;
}