Pagini recente » Cod sursa (job #2150041) | Cod sursa (job #369329) | Cod sursa (job #868360) | Cod sursa (job #2085972) | Cod sursa (job #1867663)
#include <stdio.h>
#include <iostream>
#define MAX 100000
using namespace std;
int interval[2][MAX], timp[MAX];
void insert_sort(int n)
{
int i, j, aux;
for(i = 1; i < n; i++)
{
j = i;
while(j > 0 && interval[1][j] < interval[1][j - 1])
{
aux = interval[1][j];
interval[1][j] = interval[1][j - 1];
interval[1][j - 1] = aux;
aux = interval[0][j];
interval[0][j] = interval[0][j - 1];
interval[0][j - 1] = aux;
j--;
}
}
}
int main()
{
FILE *fin, *fout;
int n, i, maxi, st, dr, mij, retinem, gasit;
fin = fopen("heavymetal.in", "r");
fout = fopen("heavymetal.out", "w");
fscanf(fin, "%d", &n);
for(i = 0; i < n; i++)fscanf(fin, "%d%d", &interval[0][i], &interval[1][i]);
insert_sort(n);
//for(i = 0; i < n; i++)printf("%d %d\n", interval[0][i], interval[1][i]);
for(i = 0; i < n; i++)
{
st = 0;
dr = i - 1;
gasit = 0;
mij = retinem = 0;
while(st <= dr && gasit == 0)
{
if(retinem == 0)retinem = -1;
mij = (st + dr) / 2;
if(interval[0][i] >= interval[1][mij])
{
st = mij + 1;
retinem = mij;
}
else dr = mij - 1;
}
if(retinem != -1)timp[i] = interval[1][i] - interval[0][i] + timp[retinem];
else timp[i] = interval[1][i] - interval[0][i];
}
//printf("\n");
//for(i = 0; i < n; i++)printf("%d\n", timp[i]);
maxi = 0;
for(i = 0; i < n; i++)if(maxi < timp[i])maxi = timp[i];
fprintf(fout, "%d", maxi);
fclose( fin );
fclose( fout );
return 0;
}