Pagini recente » Cod sursa (job #1872706) | Cod sursa (job #2614833) | Cod sursa (job #1145073) | Cod sursa (job #1710042) | Cod sursa (job #2774124)
#include <fstream>
#include <algorithm>
using namespace std;
int n;
pair<int, int> a[100001];
void read() {
int i;
ifstream f("heavymetal.in");
f >> n;
for (i = 1; i <= n; i++)
f >> a[i].first >> a[i].second;
f.close();
}
bool csort(pair<int, int> a, pair<int, int> b) {
if (a.second < b.second)
return 1;
else if (a.second == b.second && a.first < b.first)
return 1;
return 0;
}
const int Inf = -1e9 - 100;
int dp[100001];
void solve() {
int x, y, st, dr, mij;
sort(a + 1, a + n + 1, csort);
int i;
dp[0] = 0;
for (i = 1; i <= n; i++)
dp[i] = -Inf;
for (i = 1; i <= n; i++) {
x = a[i].first, y = a[i].second;
st = 1, dr = i - 1;
while (st <= dr) {
mij = (st + dr) / 2;
if (a[mij].second <= x)
st = mij + 1;
else dr = mij - 1;
}
dp[i] = max(dp[i - 1], dp[dr] + (y - x));
}
}
void output() {
ofstream g("heavymetal.out");
g << dp[n];
g.close();
}
int main() {
read();
solve();
output();
return 0;
}