Pagini recente » Cod sursa (job #2064047) | Cod sursa (job #1320364) | Cod sursa (job #2051720) | Cod sursa (job #3133150) | Cod sursa (job #282858)
Cod sursa(job #282858)
#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]=best[searci(i)]+(A[i].b-A[i].a);
ofstream g("heavymetal.out");
int maxim=-1;
for(i=0;i<=n;i++)
maxim=max(maxim, best[i]);
g<<maxim<<'\n';
g.close();
return 0;
}