Pagini recente » Cod sursa (job #156999) | simulare_de_oni_6 | Cod sursa (job #316116) | Cod sursa (job #689647) | Cod sursa (job #2167458)
#include <iostream>
#include <fstream>
#include <algorithm>
#define maxn 100005
using namespace std;
struct interval{
int st, dr;
bool operator < (const interval & a) const
{
if (dr == a.dr)
return st <= a.st;
return dr <= a.dr;
}
};
interval v[maxn];
int d[maxn];
int N;
int main()
{
ifstream in ("heavymetal.in");
ofstream out ("heavymetal.out");
in>>N;
for(int i = 1; i <= N; ++i)
{
in>>v[i].st;
in>>v[i].dr;
}
sort(v + 1, v + N + 1);
d[1] = v[1].dr - v[1].st;
for(int i = 2; i <= N; ++i)
{
int lo = 1, hi = i - 1, mid;
while(lo <= hi)
{
mid = (lo + hi)/2;
if(v[mid].dr <= v[i].st)
lo = mid + 1;
else
hi = mid - 1;
}
d[i] = max(v[i].dr - v[i].st + d[hi], d[i-1]);
}
out<<d[N];
return 0;
}