Cod sursa(job #2513311)

Utilizator DariusDCDarius Capolna DariusDC Data 22 decembrie 2019 20:48:57
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.57 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, tmax;
int dp[100005];

struct concert
{
    int a, b;
}c[100005];

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> c[i].a >> c[i].b, tmax = max(tmax, c[i].b);
    for (int i = 1; i <= tmax; i++)
    {
        dp[i] = dp[i - 1];
        for (int j = 1; j <= n; j++)
            if (c[j].b == i)
                dp[i] = max(dp[i], dp[c[j].a] + c[j].b - c[j].a);
    }
    fout << dp[tmax];
    return 0;
}