Pagini recente » Cod sursa (job #1008558) | Cod sursa (job #1142926) | Istoria paginii runda/oji_bv_2022/clasament | Cod sursa (job #698058) | Cod sursa (job #1123201)
#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 Links, int Recht, int Wert)
{
while(Links<=Recht)
{
int Mitte = (Links+Recht)/2;
if(I[Mitte].first > Wert)
Recht = Mitte - 1;
else
Links = Mitte + 1;
}
return (Links+Recht)/2;
}
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;
}