Pagini recente » Cod sursa (job #2446661) | Cod sursa (job #1495121) | Cod sursa (job #2765972) | Cod sursa (job #3130322) | Cod sursa (job #2873148)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
char buff[4096];
int pbuf=4095;
void readbuff(){
pbuf=0;fin.read(buff,4095);
}
int citire(){
int nr=0;
if(pbuf==4095){
readbuff();
}
while(buff[pbuf]<'0'||buff[pbuf]>'9'){
pbuf++;
if(pbuf==4095){
readbuff();
}
}
while(buff[pbuf]>='0'&&buff[pbuf]<='9'){
nr=nr*10+buff[pbuf]-'0';pbuf++;
if(pbuf==4095){
readbuff();
}
}
return nr;
}
struct interv{
int st,dr;
}v[100005];
bool cmp(interv x,interv y){
return x.dr<y.dr;
}
int dp[100005],max1[100005];
int main()
{
int n;n=citire();
for(int i=1;i<=n;i++){
v[i].st=citire();v[i].dr=citire();
}sort(v+1,v+n+1,cmp);int val1,val2,mij,val=0;
for(int i=1;i<=n;i++){
val1=1;val2=i-1;val=-1;
while(val2>=val1){
mij=(val1+val2)/2;
if(v[mij].dr<=v[i].st){
val=mij;val1=mij+1;
}
else{
val2=mij-1;
}
}
dp[i]=max1[val]+v[i].dr-v[i].st;
max1[i]=max(max1[i-1],dp[i]);
}fout<<max1[n]<<'\n';
return 0;
}