Pagini recente » Cod sursa (job #1796153) | Cod sursa (job #2007663) | Cod sursa (job #2843953) | Cod sursa (job #707545) | Cod sursa (job #1207030)
#include <cstdio>
#include <algorithm>
using namespace std;
struct BAND
{
int left;
int right;
};
BAND bands[10001];
int best[10001], N;
int BinSearch(int POS)
{
int Begin, End, Mid, Closest;
Begin = 0; End = N;
while(Begin <= End)
{
Mid = (Begin+End)/2;
if(bands[Mid].right < bands[POS].left)
{
Closest = Mid;
Begin = Mid+1;
}
if(bands[Mid].right > bands[POS].left) End = Mid-1;
if(bands[Mid].right == bands[POS].left) return Mid;
}
return Closest;
}
bool SortRight(BAND A, BAND B) { return A.right < B.right; }
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int i, j, pos;
scanf("%d", &N);
for(i=1; i<=N; i++) scanf("%d %d", &bands[i].left, &bands[i].right);
sort(&bands[1], &bands[N+1], SortRight);
for(i=1; i<=N; i++)
{
best[i] = best[i-1];
pos = BinSearch(i);
best[i] = max(best[i], best[pos] + bands[i].right - bands[i].left);
}
printf("%d\n", best[N]);
return 0;
}