Pagini recente » Cod sursa (job #1537619) | Cod sursa (job #2893924) | Cod sursa (job #453831) | Cod sursa (job #1789487) | Cod sursa (job #153780)
Cod sursa(job #153780)
#include <stdio.h>
#include <stdlib.h>
#define N 100012
struct timp
{
int ora,cost;
};
struct interval
{
int a,b;
};
int compar (const void*p, const void*q)
{
interval *pp=(interval*)p, *qq=(interval*)q;
interval x=*pp, y=*qq;
if(x.b<y.b)
return -1;
if(x.b>y.b)
return 1;
return 0;
}
int main()
{ interval v[N];
timp w[N];
int n,dr,i,j,k,s,sa=0,rez=0;
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w",stdout);
scanf("%d", &n);
for(i=0;i<n;++i)
scanf("%d%d", &v[i].a, &v[i].b);
qsort(v,n,sizeof(v[0]),compar);
w[0].cost=v[0].b-v[0].a;
w[0].ora=v[0].b;
for(i=1;i<n;++i)
{
if(v[i].a>=v[i-1].b)
{
w[i].cost=(v[i].b-v[i].a)+w[i-1].cost;
w[i].ora=v[i].b;
//printf("normal %d %d %d\n ",v[i].b-v[i].a,w[i-1].cost,w[i].cost);
}
else
{
for(j=i-1;j>=0;--j)
if(v[j].b<=v[i].a)
break;
//printf("%d %d ",v[j].b,v[i].a);
if(v[i].b-v[i].a+w[j].cost>w[i-1].cost)
{
for(k=j+1;k<i;++k)
{
//printf(" k=%d ", k);
w[k].cost=w[k-1].cost;
w[k].ora=w[k-1].ora;
}
//printf(" \n");
w[i].cost=(v[i].b-v[i].a)+w[j].cost;
w[i].ora=v[i].b;
}
else
{
w[i].cost=w[i-1].cost;
w[i].ora=w[i-1].ora;
}
}
//printf(" c=%d %d %d\n",w[i].cost,w[i].ora,i);
}
/*for(i=0;i<n;++i)
{
printf("%d %d %d ",i,v[i].a,v[i].b);
printf(" %d %d",w[i].cost,w[i].ora);
printf("\n");
}*/
rez=w[n-1].cost;
printf("%d\n", rez);
return 0;
}