Pagini recente » ONIS 2014, Clasament | Cod sursa (job #2928698) | Cod sursa (job #2056137) | Cod sursa (job #2799748) | Cod sursa (job #1310618)
#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(_1.B == _2.B)
return _1.A < _2.A;
return _1.B < _2.B;
}
int Search(int Left, int Right, int nr)
{
while(Left <= Right)
{
int Mid = (Left + Right) / 2;
if(S[Mid].B <= nr)
Left = Mid + 1;
else
Right = Mid - 1;
}
return Right;
}
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+1, S+N+1, Compare);
/*for(int i = 1; i <= N; i++)
{
cout << S[i].A << " " << S[i].B << "\n";
}*/
for(int i = 1; i <= N; i++)
{
DP[i] = max( DP[i-1],
DP[Search(0, i, S[i].A)] + S[i].Cost );
}
cout << DP[N];
}
int main()
{
Read();
return 0;
}