Pagini recente » Cod sursa (job #1095989) | Cod sursa (job #621837) | Cod sursa (job #2437064) | Cod sursa (job #1763336) | Cod sursa (job #214936)
Cod sursa(job #214936)
#include <stdio.h>
#include <stdlib.h>
int n,i,j,Best[100000],b[100000],a[100000],maxim,x,y,f[100000];
char ch[10];
int max(int a,int b)
{
if (a>b)
return a;
else
return b;
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
if(left != right)
{
int aux = numbers[left], randompoz = left + rand() % (left - right);
numbers[left] = numbers[randompoz];
numbers[randompoz] = aux;
}
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
int main()
{
freopen("heavymetal.in","rt",stdin);
scanf("%d", &n);
for (i=1;i<=n;++i)
{
scanf("%d %d", &a[i],&b[i]);
/*gets(ch);
x=y=j=0;
while (ch[j]!=' ')
{
x=x*10+ch[j]-'0';
j++;
}
j++;
while (ch[j])
{
y=y*10+ch[j]-'0';
j++;
}
a[i]=x;
b[i]=y; */
//f[a[i]]++;
//f[b[i]]++;
maxim=max(maxim,b[i]);
}
q_sort(a,1,n);
q_sort(b,1,n);
for (i=1;i<=maxim;++i)
{
// if (f[i]>=1)
Best[i]=Best[i-1];
for (j=1;j<=maxim;++j)
if (b[j]==i)
Best[i]=max(Best[i],Best[a[j]]+(b[j]-a[j]));
}
freopen("heavymetal.out","wt",stdout);
printf("%d", Best[maxim]);
return 0;
}