Pagini recente » Cod sursa (job #1268191) | Cod sursa (job #2917210) | Cod sursa (job #3186691) | Cod sursa (job #1476079) | Cod sursa (job #1699454)
#include <algorithm>
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct qq {
long long st , en;
} v[NMAX];
long long dp[NMAX];
long long n;
bool comp(qq a , qq b) {
return a.en < b.en || (a.en == b.en && a.st < b.st);
}
long long caut_bin(long long val);
int main() {
f >> n;
for(int i = 1 ; i <= n ; ++i) {
f >> v[i].st >> v[i].en;
}
sort(v + 1 , v + n + 1 , comp);
for(int i = 1 ; i <= n ; ++i) {
long long p = caut_bin(v[i].st);
dp[i] = dp[p] + v[i].en - v[i].st;
dp[i] = max(dp[i] , dp[i - 1]);
}
g << dp[n];
return 0;
}
long long caut_bin(long long val) {
long long i , p = 0;
for(i = 1 ; i <= n ; i <<= 1);
while(i) {
if(i + p <= n && v[i + p].en <= val) {
p += i;
}
i >>= 1;
}
return p;
}