Pagini recente » Cod sursa (job #4203) | Cod sursa (job #599148) | Cod sursa (job #3161170) | Cod sursa (job #1006105) | Cod sursa (job #339142)
Cod sursa(job #339142)
#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#define dim 100001
using namespace std;
long long Be[dim], A[dim], B[dim];
int V[dim];
long long max(long long a, long long b)
{
if(a > b) return a;
return b;
}
void qsort(long inc, long sf)
{
long long i,j,temp, aux;
i = inc;
j = sf;
temp = B[V[(i+j)/2]];
do
{ while(B[V[i]] < temp) i++;
while(B[V[j]] > temp) j--;
if(i < j) aux = V[i], V[i] = V[j], V[j] = aux;
if(i <= j) j--, i++;
} while (i <= j);
if(inc < j) qsort(inc, j);
if (i < sf) qsort(i, sf);
}
int main()
{ long long 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, "%lld%lld", &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];
//while(B[V[k]] < i) k++;
//if(B[V[k]] == i)
//{
//Be[i] = Be[i-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]]));
//}
k = B[V[i]];
}
fprintf(g, "%lld\n", Be[T]);
fclose(f);
fclose(g);
return 0;
}