Pagini recente » Cod sursa (job #2689974) | Cod sursa (job #1729979) | Cod sursa (job #2292756) | Cod sursa (job #1664976) | Cod sursa (job #1254491)
#include <stdio.h>
#define MAXN 100000
int a[MAXN+1], b[MAXN+1], s[MAXN+1], n;
inline int tata(int p){
return p/2;
}
inline int fiust(int p){
return p*2;
}
inline int fiudr(int p){
return p*2+1;
}
inline void schimba(int p1, int p2){
int aux;
aux=a[p1];
a[p1]=a[p2];
a[p2]=aux;
aux=b[p1];
b[p1]=b[p2];
b[p2]=aux;
}
inline void coborare(int p){
int f, q;
f=1;
while((f==1)&&(fiust(p)<=n)){
q=fiust(p);
if((fiudr(p)<=n)&&(b[fiudr(p)]>b[q])){
q=fiudr(p);
}
if(b[q]>b[p]){
schimba(p, q);
p=q;
}else{
f=0;
}
}
}
inline void heapify(){
int i;
for(i=tata(n); i>0; i--){
coborare(i);
}
}
inline void heapSort(){
while(n>1){
schimba(1, n);
n--;
coborare(1);
}
}
int main(){
int cn, i, rez, pas;
FILE *fin, *fout;
fin=fopen("heavymetal.in", "r");
fout=fopen("heavymetal.out", "w");
fscanf(fin, "%d", &n);
for(i=1; i<=n; i++){
fscanf(fin, "%d%d", &a[i], &b[i]);
}
cn=n;
heapify();
heapSort();
n=cn;
for(i=1; i<=n; i++){
s[i]=s[i-1];
rez=0;
for(pas=1<<16; pas!=0; pas>>=1){
if((rez+pas<i)&&(b[rez+pas]<=a[i])){
rez+=pas;
}
}
if(s[i]<s[rez]+b[i]-a[i]){
s[i]=s[rez]+b[i]-a[i];
}
}
fprintf(fout, "%d\n", s[n]);
fclose(fin);
fclose(fout);
return 0;
}