Pagini recente » Cod sursa (job #591492) | Cod sursa (job #661439) | Cod sursa (job #1616733) | Cod sursa (job #1405280) | Cod sursa (job #1466541)
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair
using namespace std;
const string name = "heavymetal",
in_file = name + ".in",
out_file = name + ".out";
ifstream fin(in_file);
ofstream fout(out_file);
const int MAX = 1e5 + 1;
struct interval {
int a, b;
interval() {}
interval(int a, int b) {
this -> a = a;
this -> b = b;
}
bool operator< (const interval& obj) const {
return b < obj.b;
}
} v[MAX];
int bs (int nr, int poz) {
int left = 1, right = poz - 1, sol = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (v[mid].b <= nr){
left = mid + 1;
sol = max(sol, mid);
} else right = mid - 1;
}
return sol;
}
int n, dp[MAX];
int main() {
fin >> n;
for (int a, b, i = 1; i <= n; i++) {
fin >> a >> b;
v[i] = interval(a, b);
}
sort(v + 1, v + n + 1);
for (int i = 1; i <= n; i++){
int poz = bs(v[i].a, i);
dp[i] = max(dp[i - 1], v[i].b - v[i].a + dp[poz]);
}
fout << dp[n];
return 0;
}