Pagini recente » Borderou de evaluare (job #39564) | Borderou de evaluare (job #1811133) | Borderou de evaluare (job #980164) | Borderou de evaluare (job #2526105) | Cod sursa (job #3240527)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");
int main() {
int N,i,j,ma,l,r,bun,md;
cin>>N;
pair<int, int> ore[N];
int m[N];
for(i=0; i<N; ++i)
cin >> ore[i].first >> ore[i].second;
sort(ore, ore+N, [](const std::pair<int, int> &left, const std::pair<int, int> &right) {
return left.second < right.second;
});
m[0]=ore[0].second-ore[0].first;
for(i=1;i<N;i++){
ma=ore[i].second-ore[i].first;
l=0;
r=i-1;
bun=-1;
while(l<=r){
md=l+(r-l)/2;
if(ore[md].second<=ore[i].first){
bun=md;
l=md+1;
}
else
r=md-1;
}
if(bun!=-1) {
ma+=m[bun];
}
m[i]=max(ma, m[i-1]);
}
cout<<m[N-1];
return 0;
}