Pagini recente » Cod sursa (job #3236554) | Cod sursa (job #95598) | Cod sursa (job #2551853) | Cod sursa (job #751372) | Cod sursa (job #138957)
Cod sursa(job #138957)
#include <stdio.h>
#define nmax 10005
struct interval
{
int in, out;
};
int N, maxim, suma[nmax];
interval A[nmax], B[nmax];
int max(int i, int j)
{
return i > j? i: j;
}
void msort(int l, int r)
{
int i, j, k;
if (l >= r) return;
int m = (l+r)/2;
msort(l, m);
msort(m+1, r);
for (i = k = l, j = m+1; i <= m && j <= r; ++k)
if (A[i].out < A[j].out || A[i].out == A[j].out && A[i].in <= A[j].in)
B[k] = A[i++];
else
B[k] = A[j++];
while (i <= m)
B[k++] = A[i++];
while (j <= r)
B[k++] = A[j++];
for (i = l; i <= r; ++i)
A[i] = B[i];
}
int binary(int l, int r, int value)
{
if (l > r) return 0;
int m = (l+r)/2;
if (A[m].out <= value)
return max(m, binary(m+1, r, value));
else
return binary(l, m-1, value);
}
int main()
{
int i;
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
scanf("%d%d", &A[i].in, &A[i].out);
msort(1, N);
for (suma[1] = A[1].out-A[1].in, i = 2; i <= N; ++i)
suma[i] = max(A[i].out - A[i].in + suma[binary(1, N, A[i].in)], suma[i-1]);
for (i = 1; i <= N; ++i)
if (suma[i] > maxim)
maxim = suma[i];
printf("%d\n", maxim);
return 0;
}