Pagini recente » Cod sursa (job #2671112) | Cod sursa (job #1100726) | Cod sursa (job #928624) | Cod sursa (job #1788213) | Cod sursa (job #184101)
Cod sursa(job #184101)
#include <stdio.h>
#include <stdlib.h>
int n, ord[1000000], best[1000000], maxim;
typedef struct
{
int a, b;
} interval;
interval a[100000], b[100000];
int max (int x, int y) { return x > y ? x : y; }
int cmp(const void *p, const void *q)
{
int x = *(int*)p, y = *(int*)q;
if (a[x].b == a[y].b) return a[x].a - a[y].a;
return a[x].b - a[y].b;
}
void citire()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int i;
scanf("%d",&n);
for (i = 0; i < n; i++)
{
scanf("%d %d",&a[i].a,&a[i].b);
ord[i] = i;
}
qsort(ord, n, sizeof(int), cmp);
for (i = 1; i <= n; i++) b[i] = a[ ord[i-1] ] ;
for (i = 1; i <= n; i++) ord[i] = i;
}
int main()
{
int i, j, x, aux;
citire();
x = b[n].b; j = 1;
for (i = 1; i <= x; i++)
{
best[i] = best[i - 1];
while(i == b[j].b)
{
aux = best[b[j].a] + b[j].b - b[j].a;
if(aux > best[i]) best[i] = aux;
j++;
}
if (best[i] > maxim) maxim = best[i];
}
printf("%d\n",maxim);
return 0;
}
/*
x=v[n-1].b;
for(i=1; i<=x; ++i)
{
best[i]=best[i-1];
while(i==v[j].b)
{
aux=best[v[j].a]+v[j].b-v[j].a;
if(aux>best[i])
best[i]=aux;
j++;
}
}*/