Pagini recente » Cod sursa (job #921911) | Cod sursa (job #902903) | Cod sursa (job #1481116) | Cod sursa (job #3194172) | Cod sursa (job #2515279)
#include<bits/stdc++.h>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int NMAX = 100001;
int n;
int dp[NMAX];
vector<pair<int, int> > intervals;
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
return (a.second < b.second);
}
int binSearch(int left, int right, int val)
{
int mid = 0, sol = -1;
while(left <= right){
mid = left + (right - left) / 2;
if(intervals[mid].second <= val){
left = mid + 1;
sol = mid;
}
else{
right = mid - 1;
}
}
if(sol >= 0){
return dp[sol];
}
return 0;
}
int main()
{
f>>n;
intervals.resize(n);
for(auto &x: intervals){
f>>x.first>>x.second;
}
sort(intervals.begin(), intervals.end(), cmp);
dp[0] = intervals[0].second - intervals[0].first;
for(int i = 1 ; i < n ; i++){
dp[i] = max(dp[i - 1], intervals[i].second - intervals[i].first + binSearch(0, i, intervals[i].first));
}
g<<dp[n - 1];
return 0;
}