Pagini recente » Cod sursa (job #99074) | Cod sursa (job #2367183) | Cod sursa (job #1810915) | Cod sursa (job #2814811) | Cod sursa (job #1312675)
#include <stdio.h>
#define MAXN 100000
int st[MAXN], dr[MAXN], rez[MAXN];
inline int max2(int a, int b){
return a > b ? a : b;
}
inline int caut(int x, int n){
int i = 0, pas = 1 << 16;
while(pas > 0){
if(i + pas < n)
if(dr[i + pas] <= x)
i += pas;
pas >>= 1;
}
if(dr[i] <= x)
return rez[i];
return 0;
}
void qs(int cst, int cdr){
int i = cst, j = cdr, piv = dr[(cst + cdr) / 2], aux;
while(i <= j){
while(dr[i] < piv)
i++;
while(dr[j] > piv)
j--;
if(i <= j){
aux = st[i];
st[i] = st[j];
st[j] = aux;
aux = dr[i];
dr[i] = dr[j];
dr[j] = aux;
i++;
j--;
}
}
if(cst < j)
qs(cst, j);
if(i < cdr)
qs(i, cdr);
}
int main(){
FILE *in = fopen("heavymetal.in", "r");
int n, i;
fscanf(in, "%d", &n);
for(i = 0; i < n; i++)
fscanf(in, "%d%d", &st[i], &dr[i]);
fclose(in);
qs(0, n - 1);
int el;
for(i = 0; i < n; i++){
if(i != 0)
rez[i] = max2(rez[i - 1], dr[i] - st[i] + caut(st[i], n));
else
rez[i] = dr[i] - st[i];
}
FILE *out = fopen("heavymetal.out", "w");
fprintf(out, "%d", rez[n - 1]);
fclose(out);
return 0;
}