Pagini recente » Cod sursa (job #2784953) | Cod sursa (job #842476) | Profil MihaelaCismaru | Cod sursa (job #1274847) | Cod sursa (job #2497984)
#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);
}
void Solve() {
DP[1] = V[1].len;
for (int i = 2; i <= N; i++) {
for (int j = i-1; j >= 1; j--)
if(V[i].A >= V[j].B)
DP[i] = DP[j] + V[i].len, j=0;
DP[i] = max(DP[i], DP[i-1]);
}
out << DP[N];
}
int main() {
Read();
Solve();
}