Pagini recente » Cod sursa (job #2841126) | Cod sursa (job #2817678) | Cod sursa (job #2717771) | Cod sursa (job #736653) | Cod sursa (job #140670)
Cod sursa(job #140670)
#include <stdio.h>
#include <stdlib.h>
int n, best[1000], nr, ord[1000];
typedef struct
{
int x, y;
} interv;
interv a[1000], b[1000];
int cmp(const void *a, const void *c)
{
int x = *(int*)a, y = *(int*)c;
if (b[x].y == b[y].y) return b[x].x - b[y].x;
else return b[x].y - b[y].y;
}
inline max(int x, int y) {return x > y ? x : y;}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int i, j, k;
scanf("%d",&n);
for (i = 0; i < n; i++){ scanf("%d %d",&b[i].x, &b[i].y); ord[i] = i;}
qsort(ord,n,sizeof(int),cmp);
for (i = 0; i < n; i++) a[i + 1] = b[ord[i]];
for (i = 1; i <= n; i++)
{
if (!best[i])
{
best[i] = best[i - 1];
for (j = i; a[j].y == a[i].y; j++)
{
for (k = i; best[k] > a[j].x; k--);
best[i] = max(best[i], best[k] + (a[j].y - a[j].x));
}
}
}
printf("%d",best[n]);
return 0;
}