Pagini recente » Cod sursa (job #2649908) | Cod sursa (job #1287497) | Cod sursa (job #3268865) | Cod sursa (job #1440711) | Cod sursa (job #2864905)
#include <fstream>
#include <algorithm>
using namespace std;
pair<int, int> s[100010];
int d[100010];
int n, maxim;
int main () {
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
fin>>n;
for (int i=1;i<=n;i++){
fin>>s[i].second>>s[i].first;
}
sort(s+1, s+n+1);
for (int i=1;i<=n;i++){
d[i]=s[i].first-s[i].second;
int st=1;
int dr=i-1;
while (st<=dr){
int mid = (st+dr)/2;
if (s[i].second>=s[mid].first){
st=mid+1;
}
else{
dr=mid-1;
}
}
d[i]=max(d[i], d[dr]+s[i].first-s[i].second);
if (d[i]>maxim){
maxim=d[i];
}
}
fout<<maxim;
return 0;
}