Pagini recente » Cod sursa (job #693618) | Cod sursa (job #1679286) | Cod sursa (job #3197633) | Cod sursa (job #23705) | Cod sursa (job #2060176)
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMax = 100005;
const int inf = 0x3f3f3f3f;
int N, dp[NMax];
struct Trupa
{
int low, high;
}v[NMax];
void Read()
{
fin >> N;
for(int i=1; i<=N; ++i)
fin >> v[i].low >> v[i].high;
}
bool cmp(Trupa A, Trupa B)
{
if(A.high == B.high)
return A.low < B.low;
return A.high < B.high;
}
int Caut_Bin(int x)
{
int st = 0;
int dr = x - 1;
int mij;
while(st <= dr)
{
mij = (st + dr) / 2;
if (v[mij].high <= v[x].low)
st = mij + 1;
else
dr = mij - 1;
}
return dr;
}
void Solve()
{
sort(v+1, v+N+1, cmp);
for(int i=1; i<=N; ++i)
{
dp[i] = max(v[i].high - v[i].low + dp[Caut_Bin(i)], dp[i-1]);
}
fout << dp[N];
}
int main()
{
Read();
Solve();
return 0;
}