Pagini recente » Cod sursa (job #2004037) | Istoria paginii runda/simulare-cartita-51b/clasament | Autentificare | Cod sursa (job #872764) | Cod sursa (job #1006040)
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 100010;
int N, Best[NMAX], Max[NMAX];
pair<int, int> V[NMAX];
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%i", &N);
for(int i = 1; i <= N; ++ i)
scanf("%i %i", &V[i].second, &V[i].first);
V[0] = make_pair(0, 0);
sort(V, V + N + 1);
for(int i = 1; i <= N; ++ i)
{
int Left = 0, Right = i - 1, Mid, Pos;
while(Left <= Right)
{
Mid = (Left + Right) / 2;
if(V[Mid].first <= V[i].second) Pos = Mid, Left = Mid + 1;
else Right = Mid - 1;
}
Best[i] = Max[Pos] + V[i].first - V[i].second;
Max[i] = max(Max[i - 1], Best[i]);
}
printf("%i\n", Max[N]);
return 0;
}