Pagini recente » Cod sursa (job #1248270) | Cod sursa (job #308368) | Cod sursa (job #709275) | Cod sursa (job #2977455) | Cod sursa (job #2729090)
// problema heavymetal
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#define NMax 100000
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
struct secv {
int a, b;
};
vector<int> pozitii, paux, DP;
vector<secv> secvente;
void input() {
int a, b;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> a >> b;
secvente.push_back({a, b});
paux.push_back(a);
paux.push_back(b);
}
}
int findpos(int pos) {
return lower_bound(pozitii.begin(), pozitii.end(), pos) - pozitii.begin();
}
void init() {
auto f = [](secv x, secv y) {
if (x.b < y.b) return 1;
if (x.b > y.b) return 0;
if (x.a <= y.a) return 1;
return 0;
};
sort(secvente.begin(), secvente.end(), f);
//
sort(paux.begin(), paux.end());
for (auto p = paux.begin(); p < paux.end(); ++p) {
pozitii.push_back(*p);
while (*p == *(p + 1)) ++p;
}
//
auto ps = secvente.begin();
auto ppoz = pozitii.begin();
int a, b;
DP.push_back(0);
for (++ppoz; ppoz < pozitii.end(); ++ppoz) {
for (; (*ps).b < *ppoz; ++ps);
b = ppoz - pozitii.begin();
DP.push_back(DP[b - 1]);
for (; (*ps).b == *ppoz; ++ps) {
a = findpos((*ps).a); // unde se afla "a"
DP[b] = max(DP[b], DP[a] + (*ps).b - (*ps).a);
}
}
}
void solve() {
fout << *(DP.end() - 1);
}
int main() {
input();
init();
solve();
}