Pagini recente » Cod sursa (job #2687618) | Cod sursa (job #1439447) | Cod sursa (job #2786466) | Cod sursa (job #1295013) | Cod sursa (job #247392)
Cod sursa(job #247392)
#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-1;
int mij;
while(p!=u)
{mij=(p+u)>>1;
if(v[mij].b>=val)
u=mij;
else
{p=mij+1;
if(v[mij].b<val&&v[mij+1].b>val)
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(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;}