Pagini recente » Cod sursa (job #807820) | Cod sursa (job #2415213) | Cod sursa (job #409692) | Cod sursa (job #2132204) | Cod sursa (job #247684)
Cod sursa(job #247684)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct concert{unsigned long long int a,b;}v[100000];
unsigned long long int i,max,j,k,l,m,n,best[100000];
/*int caut(int val)
{int p=0,u=i;
int mij;
while(p+1<u)
{mij=(p+u)>>1;
if(v[mij].b>val)
u=mij;
else
if(v[mij]< val)
p=mij+1;
else
return mij;
}
return p;}*/
int cmp(concert a,concert b)
{return a.b<b.b;}
int main(){
FILE *f=fopen("heavymetal.in","r");
fscanf(f,"%lld",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lld %lld",&v[i].a,&v[i].b);
fclose(f);
best[0]--;
sort(v,v+n+1,cmp);
best[1]=v[1].b-v[1].a;
for(i=2;i<=n;i++)
{best[i]=best[i-1];
//j=caut(v[i].a);
//if(v[j].b<=v[i].a)
for(j=1;j<=i;j++)
if(v[i].a>=v[j].b)
if(best[i]<(best[j]+v[i].b-v[i].a))
best[i]=best[j]+v[i].b-v[i].a;
}
FILE *g=fopen("heavymetal.out","w");
fprintf(g,"%lld",best[n]);
fclose(g);
return 0;}