Pagini recente » Cod sursa (job #1925806) | Cod sursa (job #1285463) | Cod sursa (job #770648) | Cod sursa (job #398830) | Cod sursa (job #1123184)
#include <cstdio>
#include <algorithm>
using namespace std;
#define NMAX 100005
#define maxim(a,b) ((a>b)?(a):(b))
int N;
int DP[NMAX];
pair < int , int > I[NMAX];
void Scannen()
{
freopen("heavymetal.in","r",stdin);
scanf("%d",&N);
for(int i=1,x,y;i<=N;i++)
{
scanf("%d%d",&x,&y);
I[i].first = y;
I[i].second = x;
}
}
int Suche(int start, int finish, int val)
{
if(start == finish)
return start-1;
int mid = (start + finish) / 2;
if(I[mid].first > val)
return Suche(start, mid, val);
return Suche(mid + 1, finish, val);
}
void Losen()
{
sort(I+1,I+N+1);
for(int i=1;i<=N;i++)
DP[i] = maxim(DP[i - 1], DP[Suche(0,i,I[i].second)] + I[i].first - I[i].second);
}
void Druken()
{
freopen("heavymetal.out", "w", stdout);
printf("%d\n", DP[N]);
}
int main()
{
Scannen();
Losen();
Druken();
return 0;
}