Pagini recente » Cod sursa (job #248029) | Cod sursa (job #115637) | Cod sursa (job #1670968) | Cod sursa (job #1746957) | Cod sursa (job #158147)
Cod sursa(job #158147)
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define PII pair<int,int>
#define x first
#define y second
#define MAXN 100100
int N, T[MAXN];
vector< PII > A;
int solve(void)
{
int i, j, k; vector< PII >::iterator it;
sort(A.begin(), A.end());
for(i = N-1; i >= 0; i--)
{
T[i] = T[i+1], it = lower_bound(A.begin(), A.end(), mp(A[i].y,0));
T[i] = max(T[i], A[i].y-A[i].x+T[(int)(it-A.begin())]);
}
return T[0];
}
int main(void)
{
freopen("heavymetal.in", "rt", stdin);
freopen("heavymetal.out", "wt", stdout);
int i, a, b;
scanf("%d\n", &N);
for(i = 1; i <= N; i++) scanf("%d %d\n", &a, &b), A.pb(mp(a,b));
printf("%d\n", solve());
return 0;
}