Pagini recente » Cod sursa (job #781623) | Cod sursa (job #2079460) | Cod sursa (job #1148743) | Cod sursa (job #2870929) | Cod sursa (job #2497968)
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMax = 100000;
int dp[NMax + 5];
int n;
struct Formatie
{
int start, end;
} form[NMax + 5];
bool operator < (Formatie a, Formatie b)
{
if(a.end != b.end)
return a.end < b.end;
else
return a.start < b.start;
}
void read()
{
fin >> n;
for(int i = 1; i <= n; i++)
fin >> form[i].start >> form[i].end;
sort(form + 1, form + n + 1);
}
int main()
{
read();
for (int i = 1; i <= n; i++)
{
int inceput = form[i].start;
int durata = form[i].end - form[i].start;
int j;
for(j = i - 1; j > 0; j--)
if(form[j].end <= inceput)
break;
dp[i] = max(dp[i - 1], dp[j] + durata);
}
fout << dp[n];
}