Pagini recente » Cod sursa (job #1093339) | Cod sursa (job #2176995) | Cod sursa (job #450247) | Cod sursa (job #1332931) | Cod sursa (job #167911)
Cod sursa(job #167911)
#include <stdio.h>
#define NM 100001
int n, tmax;
int t[NM];
int i, j, k;
int a[NM], b[NM];
void Qsort(int st, int dr);
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &n);
for ( i = 1; i <= n; i++ )
scanf("%d %d", &a[i], &b[i]);
Qsort(1, n);
for ( i = 1; i <= n; i++ )
{
t[i] = b[i]-a[i];
for ( j = i-1; j >= 1; j-- )
if ( a[i] >= b[j] && t[i] < t[j] + (b[i]-a[i]) )
t[i] = t[j] + b[i]-a[i];
if ( tmax < t[i] ) tmax = t[i];
}
printf("%d\n", tmax);
return 0;
}
void Qsort(int st, int dr)
{
int i = st-1;
int j = dr+1;
do
{
do { i++; } while ( b[i] < b[st] || (b[i] == b[st] && a[i] > a[st]) );
do { j--; } while ( b[st] < b[j] || (b[st] == b[j] && a[st] > a[j]) );
if ( i <= j )
{
int aux = a[i]; a[i] = a[j]; a[j] = aux;
aux = b[i]; b[i] = b[j]; b[j] = aux;
}
} while ( i <= j );
if ( i < dr ) Qsort(i, dr);
if ( st < j ) Qsort(st, j);
}