Pagini recente » Cod sursa (job #2661637) | Cod sursa (job #2278256) | Cod sursa (job #1213911) | Cod sursa (job #1815795) | Cod sursa (job #2049850)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int dp[100001];
struct str{
int x,y;
}c[100001];
int st, dr, mid,n;
bool cmp ( str s1, str s2) {
if (s1.y < s2.y)
return 1;
if (s1.y > s2.y)
return 0;
return s1.x < s2.x;
}
int main(void){
in >> n;
for (int i = 1; i <= n; i ++) {
in >> c[i].x >> c[i].y;
}
sort (c + 1, c + n + 1, cmp);
for (int i = 1; i <= n; i ++) {
for ( st = 1, dr = i; st <= dr; ) {
mid = (st + dr) >> 1;
if (c[mid].y >= c[i].x) {
st = mid + 1;
}
else{
dr = mid - 1;
}
}
dp[i] = max (dp[i-1], dp[st] + (c[i].y-c[i].x+1));
}
out << dp[n];
}