Pagini recente » Cod sursa (job #1320664) | Cod sursa (job #559218) | Cod sursa (job #1564856) | Cod sursa (job #182764) | Cod sursa (job #1207051)
#include <cstdio>
#include <algorithm>
using namespace std;
struct BAND
{
int left;
int right;
};
BAND bands[100001];
int best[100001];
int N;
int BinSearch(int Key, int Begin, int End)
{
int Mid, Closest=0;
while(Begin <= End)
{
Mid = (Begin+End)/2;
if(bands[Mid].right <= Key)
{
Closest = Mid;
Begin = Mid+1;
}
else End = Mid-1;
}
return Closest;
}
bool SortRight(BAND A, BAND B)
{
if(A.right == B.right) return A.left > B.left;
return A.right < B.right;
}
int main()
{
FILE *in = fopen("heavymetal.in", "r");
FILE *out = fopen("heavymetal.out", "w");
int i, pos, x, y;
fscanf(in, "%d", &N);
for(i=1; i<=N; i++)
{
fscanf(in, "%d %d", &x, &y);
bands[i].left = x;
bands[i].right = y;
}
sort(&bands[1], &bands[N+1], SortRight);
best[1] = bands[1].right - bands[1].left;
for(i=2; i<=N; i++)
{
best[i] = best[i-1];
pos = BinSearch(bands[i].left, 1, i-1);
best[i] = max(best[i], best[pos] + bands[i].right - bands[i].left);
}
fprintf(out, "%d\n", best[N]);
return 0;
}