Pagini recente » Cod sursa (job #1936264) | Cod sursa (job #1780485) | Cod sursa (job #1572597) | Cod sursa (job #2831931) | Cod sursa (job #1852789)
#include <cstdio>
#include <algorithm>
struct interval
{
int in,sf;
};
const int NMAX=100001;
interval v[NMAX+1];
bool cmp(interval a,interval b)
{
if(a.sf==b.sf)
return a.in<b.in;
return a.sf<b.sf;
}
int Search(int val,int in,int sf)
{
int st=in,dr=sf;
int rasp=0;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v[mij].sf>=val)
{
rasp=mij;
dr=mij-1;
}
else
{
st=mij+1;
}
}
return st;
}
int d[NMAX+1];
int main()
{
FILE *in=fopen("heavymetal.in","r");
int n;
fscanf(in,"%d ",&n);
for(int i=1;i<=n;i++)
{
fscanf(in,"%d %d ",&v[i].in,&v[i].sf);
}
fclose(in);
std::sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++)
{
int st=Search(v[i].in,1,n),dr=i;
d[i]=std::max(d[i-1],d[st]+(v[i].sf-v[i].in));
}
FILE *out=fopen("heavymetal.out","w");
fprintf(out,"%d\n",d[n]);
fclose(out);
return 0;
}