Cod sursa(job #2513311)
| Utilizator | 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;
}
