Pagini recente » Cod sursa (job #1263405) | Cod sursa (job #527447) | Cod sursa (job #1555057) | Cod sursa (job #3281931) | Cod sursa (job #282860)
Cod sursa(job #282860)
#include<fstream>
#include<algorithm>
using namespace std;
#define MAXN 100001
struct Interval{
int a, b;
};
Interval A[MAXN];
int best[MAXN];
int n;
bool cmp(Interval a1, Interval a2){
return ( ( a1.b ) < ( a2.b ) ) ;
}
inline int max(int (a), int (b)){
return ( a ) > ( b ) ? ( a ) : ( b ) ;
}
int searci(int x){
int i, pas;
for(pas=1;pas<=x;pas<<=1);
for(i=0;pas;pas>>=1)
if(i+pas<x&&A[i+pas].b<=A[x].a)
i+=pas;
return i;
}
int main(){
int i;
ifstream f("heavymetal.in");
f>>n;
A[0].a=A[0].b=0;
for(i=1;i<=n;i++)
f>>A[i].a>>A[i].b;
f.close();
sort(A, A+n+1, cmp);
for(i=1;i<=n;i++)
best[i]=max(best[searci(i)]+(A[i].b-A[i].a), best[i-1]);
ofstream g("heavymetal.out");
g<<best[n]<<'\n';
g.close();
return 0;
}