Pagini recente » Cod sursa (job #568944) | Cod sursa (job #509263) | Cod sursa (job #2260035) | Cod sursa (job #1770638) | Cod sursa (job #1310583)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMax = 100005;
struct Spectacol
{
int A, B, Cost;
}S[NMax];
int N;
int DP[NMax];
int Compare(Spectacol _1, Spectacol _2) //Aparent, se pot face variabile ce incep cu "_" ... Smecher
{
if(_2.B > _1.B)
return 1;
return 0;
}
int Search(int Left, int Right, int nr)
{
int Sol = 0;
while(Left < Right)
{
int Mid = (Left + Right) / 2;
if(S[Mid].B >= nr)
{
Sol = Mid;
Right = Mid - 1;
}
else
Left = Mid + 1;
}
if(Left == Right) return Sol;
}
void Read()
{
fin >> N;
for(int i = 1; i <= N; i++)
{
fin >> S[i].A >> S[i].B;
S[i].Cost = S[i].B - S[i].A;
}
sort(S, S+N+1, Compare);
//DP[1] = S[1].Cost;
for(int i = 1; i <= N; i++)
{
DP[i] = max( DP[i-1],
DP[Search(1, i, S[i].A)] + S[i].Cost );
}
cout << DP[N];
}
int main()
{
Read();
return 0;
}