Pagini recente » Cod sursa (job #574543) | Cod sursa (job #1736337) | Cod sursa (job #2145936) | Cod sursa (job #1154872) | Cod sursa (job #762056)
Cod sursa(job #762056)
#include <fstream>
#include <algorithm>
#define DIM 100001
#define INF 0x3f3f3f3f
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int N;
long long best[DIM], maxim; // durata maxima ce se poate obtine pana la spectacolul i
struct show
{
int start, end, dif;
}s[DIM];
bool comp(const show &unu, const show &doi)
{
if( unu.end == doi.end )
{
return unu.start < doi.start;
}
return unu.end < doi.end;
}
int main()
{
int i, j;
in >> N;
for(i = 1; i <= N; i++)
{
in >> s[i].start >> s[i].end;
s[i].dif = s[i].end - s[i].start;
}
sort(s+1, s+N+1, comp);
best[1] = s[1].dif;
for(i = 2; i <= N; i++)
{
maxim = -INF;
for(j = 1; j < i; j++)
{
if( s[i].start >= s[j].end )
{
if( best[j] > maxim )
{
maxim = best[j];
}
}
}
best[i] = s[i].dif + maxim;
}
maxim = -INF;
for(i = 1; i <= N; i++)
{
if( best[i] > maxim )
{
maxim = best[i];
}
}
out << maxim;
return 0;
}