Pagini recente » Clasament preoji2016sim | Cod sursa (job #1386148) | Cod sursa (job #1351443) | Cod sursa (job #1207592) | Cod sursa (job #2053349)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100002;
int n;
pair<int, int> band[MAXN];
int dp[MAXN];
void read() {
scanf("%d ", &n);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d\n", &x, &y);
band[i] = { x, y };
}
}
int binSearch(int left, int right, int value) {
int result = -1;
while (left <= right) {
int middle = (left + right) / 2;
if(band[middle].second <= value)
result = middle, left = middle + 1;
else right = middle - 1;
}
return result;
}
void solve() {
int result = 0;
for (int i = 1; i <= n; i++) {
int pos = binSearch(1, n, band[i].first);
dp[i] = max(dp[i - 1], dp[pos] + band[pos].second - band[pos].first);
result = max(result, dp[i]);
}
cerr << result << endl;
}
int main() {
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
read();
sort(band + 1, band + n + 1);
solve();
return 0;
}