Pagini recente » Diferente pentru problema/drumuri3 intre reviziile 11 si 18 | Diferente pentru utilizator/bureac intre reviziile 2 si 3 | Atasamentele paginii Algoritmiada 2013 - Runda 4, Clasele 5-9 | Diferente pentru problema/ttg intre reviziile 12 si 8 | Cod sursa (job #2445866)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, best[100005], maxim;
struct intervalPuscarie // :)))
{
int x, y;
}v[100005];
bool cmp(intervalPuscarie a, intervalPuscarie b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
for (int i = 1; i <= n; ++i)
{
best[i] = v[i].y - v[i].x;
}
for (int i = 2; i <= n; ++i)
{
int maxx = best[i];
for (int j = 1; j < i; ++j)
{
if (v[j].y <= v[i].x)
{
maxx = max(maxx, best[i] + best[j]);
}
}
best[i] = maxx;
maxim = max(maxim, best[i]);
}
fout << maxim;
return 0;
}