Pagini recente » Cod sursa (job #155461) | Cod sursa (job #2464056) | Cod sursa (job #1629375) | Cod sursa (job #2956707) | Cod sursa (job #142332)
Cod sursa(job #142332)
#include<stdio.h>
typedef struct {
long x, y;
}Spectacol;
Spectacol *v, aux;
long n, i, *L, *poz;
long max, pozj, j, s=0;
void citire(){
freopen("heavymetal.in","r",stdin);
scanf("%ld",&n);
v=new Spectacol[n+1];
L=new long[n+1];
poz=new long[n+1];
for(i=1; i<=n; i++) scanf("%ld %ld\n", &v[i].x, &v[i].y);
fclose(stdin);
}
void qsort(int x, int y){
int i=x, j=y, mx, my;
mx=v[(x+y)/2].x;
my=v[(x+y)/2].y;
while(i<=j){
while( (v[i].y<my) || (v[i].y==my && v[i].x<mx) ) i++;
while( (v[j].y>my) || (v[j].y==my && v[j].x>mx) ) j--;
if(i<=j){
aux=v[i];
v[i]=v[j];
v[j]=aux;
i++;
j--;
}
}
if(x<j) qsort(x,j);
if(i<y) qsort(i,y);
}
void apd(){
L[1]=v[1].y-v[1].x;
poz[1]=0;
for(i=2; i<=n; i++){
L[i]=v[i].y-v[i].x;
max=0;
for(j=1; j<i; j++){
if(L[j]>max && v[j].y<=v[i].x){
max=L[j];
pozj=j;
}
}
L[i]+=L[pozj];
poz[i]=pozj;
}
}
void solutie(){
//s=0;
//for(i=n; i>=1; i=poz[i]) s+=L[i];
freopen("heavymetal.out","w",stdout);
printf("%ld\n",L[n]);
fclose(stdout);
}
int main(){
citire();
qsort(1,n);
apd();
solutie();
return 0;
}