Pagini recente » Cod sursa (job #1708770) | Cod sursa (job #43932) | Cod sursa (job #986868) | Cod sursa (job #1605894) | Cod sursa (job #2642444)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 100000
struct elem{
int st;
int dr;
int lung;
};
struct elem v[NMAX+1];
bool comp(elem a,elem b){
if(a.dr<b.dr){
return true;
}
else if(a.dr==b.dr&&a.st<b.st){
return true;
}
return false;
}
int d[NMAX+1];
int cbin(int i){
int st,dr,mij;
st=0;
dr=i-1;
while(st<dr){
mij=(st+dr)/2;
if(v[mij].dr<=v[i].st){
st=mij+1;
}
else{
dr=mij-1;
}
}
}
int main()
{
FILE *fin,*fout;
fin=fopen("heavymetal.in","r");
fout=fopen("heavymetal.out","w");
int n,i,poz;
fscanf(fin,"%d",&n);
for(i=0;i<n;i++){
fscanf(fin,"%d%d",&v[i].st,&v[i].dr);
v[i].lung=v[i].dr-v[i].st;
}
std::sort(v,v+n,comp);
for(i=0;i<n;i++){
poz=cbin(i);
d[i]=std::max(d[poz]+v[i].lung,d[i-1]);
}
fprintf(fout,"%d",d[n-1]);
fclose(fin);
fclose(fout);
return 0;
}