Nu aveti permisiuni pentru a descarca fisierul grader_test18.ok
Cod sursa(job #522079)
Utilizator | Data | 14 ianuarie 2011 11:21:23 | |
---|---|---|---|
Problema | Heavy metal | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.85 kb |
#include<stdio.h>
#include<stdlib.h>
struct casy
{
long x,y;
};
casy a[10001];
long cost[10001];
long max(long b,long c)
{
if(c>=b)
return c;
return b;
}
long cb(long dr,long c)
{
long last=0,st,m;
st=1;
while(st<=dr)
{
m=(st+dr)>>1;
if(a[m].y<=c)
{
last=m;
st=m+1;
}
else
dr=m-1;
}
return last;
}
int comp(const void *c,const void *b)
{
casy *pc,*pb;
pc=(casy*)c;
pb=(casy*)b;
if(pc->y>pb->y)
return 1;
if(pc->y==pb->y)
return 0;
return -1;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
long n,i;
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld%ld",&a[i].x,&a[i].y);
qsort(a+1,n,sizeof(a[0]),comp);
cost[1]=a[1].y-a[1].x;
for(i=2;i<=n;i++)
cost[i]=max(cost[i-1],a[i].y-a[i].x+cost[cb(i-1,a[i].x)]);
printf("%ld\n",cost[n]);
return 0;
}