Pagini recente » Cod sursa (job #2504079) | Cod sursa (job #1007483) | Cod sursa (job #1566422) | Cod sursa (job #2107561) | Cod sursa (job #339312)
Cod sursa(job #339312)
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#define dim 100001
using namespace std;
int Be[dim], A[dim], B[dim];
int V[dim];
int max(int a, int b)
{
return a > b ? a : b;
}
int part(int in, int sf)
{
int x,aux,p,i,j;
p = in;
//p = (rand()%(sf-in)+in);
x = B[V[p]];
i = p;
for(j = p+1; j <= sf; j++)
if(B[V[j]] <= x)
{
i++;
aux = V[i], V[i] = V[j], V[j] = aux;
}
aux = V[p], V[p] = V[i], V[i] = aux;
return i;
}
void qsort(int in, int sf)
{ int q;
if(in < sf)
{
q = part(in, sf);
qsort(in, q-1);
qsort(q+1, sf);
}
}
int main()
{ int T;
int i,j,k,N,t;
FILE *f = fopen("heavymetal.in", "r");
FILE *g = fopen("heavymetal.out", "w");
fscanf(f, "%d", &N);
for(i = 1; i <= N; i++)
{
fscanf(f, "%d%d", &A[i], &B[i]);
V[i] = i;
}
qsort(1, N);
T = B[V[N]];
k = 1;
for(i = 1; i <= N; i++)
{
for(t = k+1; t < B[V[i]]; t++)
Be[t] = Be[t-1];
for(j = 1; j <= N; j++)
if(B[V[j]] == B[V[i]])
Be[B[V[i]]] = max(Be[B[V[i]]], Be[A[V[j]]] + (B[V[j]] - A[V[j]]));
else if(B[V[j]] > B[V[i]]) break;
k = B[V[i]];
}
fprintf(g, "%d\n", Be[T]);
fclose(f);
fclose(g);
return 0;
}