Pagini recente » Istoria paginii runda/oni_2005_1_10/clasament | Istoria paginii runda/cnrv_3/clasament | Cod sursa (job #1569695) | Istoria paginii runda/cnmnarad2/clasament | Cod sursa (job #2049856)
#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) {
return s1.y < s2.y;
}
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 = 0, dr = i; st < dr; ) {
mid = (st + dr + 1) >> 1;
if (c[mid].y <= c[i].x) {
st = mid ;
}
else{
dr = mid - 1;
}
}
dp[i] = max (dp[i-1], dp[st] + (c[i].y-c[i].x));
}
out << dp[n];
}