Pagini recente » Cod sursa (job #3363746) | Cod sursa (job #3362706) | Cod sursa (job #3364078) | Cod sursa (job #3362709) | Cod sursa (job #3363969)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, dp[200003]; ///dp[i] = durata max daca termin la o poz <= i
vector<int> aux;
struct Iris {
int st, dr, lung;
}v[100003];
inline int cmp(Iris &a, Iris &b) { return a.dr < b.dr; }
int main()
{
fin >> n;
for(int i=1; i<=n; i++) {
fin >> v[i].st >> v[i].dr;
v[i].lung = v[i].dr - v[i].st;
aux.push_back(v[i].st);
aux.push_back(v[i].dr);
}
sort(aux.begin(), aux.end());
vector<int>::iterator it = unique(aux.begin(), aux.end());
aux.resize(distance(aux.begin(), it));
for(int i=1; i<=n; i++) {
v[i].st = lower_bound(aux.begin(), aux.end(), v[i].st) - aux.begin() + 1;
v[i].dr = lower_bound(aux.begin(), aux.end(), v[i].dr) - aux.begin() + 1;
}
sort(v+1, v+n+1, cmp);
int idx = 1;
for(int i=1; i<=v[n].dr; i++) {
dp[i] = dp[i - 1];
while(v[idx].dr == i) dp[i] = max(dp[i], dp[v[idx].st] + v[idx].lung), idx++;
}
fout << dp[v[n].dr];
return 0;
}