Pagini recente » Cod sursa (job #1727253) | Cod sursa (job #657297) | Cod sursa (job #2559622) | Cod sursa (job #624474) | Cod sursa (job #2122267)
#include <fstream>
#include <algorithm>
#define st first
#define dr second
using namespace std;
pair<int, int> v[100010];
int D[100010];
int n, i, p, u, mid;
int cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int main () {
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
fin>>n;
for (i=1;i<=n;i++) {
fin>>v[i].st>>v[i].dr;
}
sort(v, v+n+1, cmp);
D[0] = 0;
for (i=1;i<=n;i++) {
/// caut cea mai mare valoare cu dr <= v[i].st
D[i] = D[i-1];
p = 0; u = i-1;
while (p <= u) {
int mid = (p+u)/2;
if (v[mid].dr <= v[i].st)
p = mid + 1;
else
u = mid - 1;
}
D[i] = max(D[i], D[u] + v[i].dr - v[i].st);
}
fout<<D[n];
return 0;
}