Pagini recente » Cod sursa (job #3285466) | Cod sursa (job #595591) | Cod sursa (job #2617274) | Cod sursa (job #1659638) | Cod sursa (job #3201466)
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int NMax = 100000;
int N, A[NMax+5], B[NMax+5], DP[NMax+5];
struct heavy {
int A, B, len;
}V[NMax+5];
bool cmp(heavy x, heavy y) {
return x.B < y.B;
}
void Read() {
in >> N;
for (int i = 1; i <= N; i++) {
in >> V[i].A >> V[i].B;
V[i].len = V[i].B - V[i].A;
}
sort(V+1, V+N+1, cmp);
}
int binarysearch(int Val, int End) {
int lo = 1, hi = End, Sol = -1;
while (lo <= hi) {
int mid = (lo+hi) / 2;
if (V[mid].B <= Val)
Sol = mid,lo = mid + 1;
else
hi = mid - 1;
}
return Sol;
}
void Solve() {
for (int i = 1; i <= N; i++) {
DP[i] = max(DP[binarysearch(V[i].A,i-1)] + V[i].len, DP[i-1]);
}
out << DP[N];
}
int main() {
Read();
Solve();
}