Pagini recente » Cod sursa (job #301947) | Cod sursa (job #1667802) | Cod sursa (job #2296536) | Cod sursa (job #2223507) | Cod sursa (job #1848692)
/**
code by purplecoder
*/
#include <fstream>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int MAX = 1e6 + 5;
int n, dp[MAX];
struct spect{
int st, dr;
}v[MAX];
bool cmp(spect a, spect b){
return a.dr < b. dr;
}
int main()
{
cin>>n;
for(int i=1; i<=n; ++i)
cin>>v[i].st>>v[i].dr;
sort(v + 1, v+n+1, cmp);
for(int i=1; i<=n; ++i){
dp[i] = d[i-1];
int st = 1, dr = i-1;
while(st <= dr){
int mij = (st + dr) / 2;
if(v[mij].dr <= v[i].st)
st = mij + 1;
else
dr = mij - 1;
}
if(dp[i] < v[i].dr - v[i].st + 1 + dp[dr])
dp[i] = v[i].dr - v[i].st + 1 + dp[dr];
}
cout<<dp[n];
return 0;
}