Pagini recente » Cod sursa (job #2631531) | Cod sursa (job #647377) | Cod sursa (job #1798018) | Cod sursa (job #1944538) | Cod sursa (job #2049316)
#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-1; 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));
}
out << dp[n];
}