Pagini recente » Atasamentele paginii Clasament hatz | Istoria paginii runda/splunge6 | Diferente pentru runda/vot/voteaza_gigel intre reviziile 5 si 6 | Istoria paginii utilizator/upt_stefan_marinescu_kolumban | Cod sursa (job #1310588)
#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 s,int e,int lim)
{
if(s==e)
return s-1;
int m=(s+e)/2;
if(S[m].B>lim)
return Search(s,m,lim);
return Search(m+1,e,lim);
}
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;
}