Pagini recente » Cod sursa (job #1589123) | Cod sursa (job #2503238) | Cod sursa (job #2180395) | Cod sursa (job #2346838) | Cod sursa (job #2106419)
#include <bits/stdc++.h>
using namespace std;
const int nmax = 100000;
struct concert
{
int s,f;
}v[1+nmax];
int sf[1+nmax];
long long dp[1+nmax];
bool cmp(concert a,concert b)
{
return a.f < b.f;
}
int m;
int caut(int x)
{
int r = 0,pas = 1 << 16;
while(pas)
{
if((r+pas) <= m && x >= sf[r+pas])
r += pas;
pas /= 2;
}
return r;
}
int main()
{
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n;
cin >> n;
for(int i = 1;i <= n;i ++)
cin >> v[i].s >> v[i].f;
sort(v+1,v+n+1,cmp);
for(int i = 1;i <= n;i ++)
{
if(v[i].f != v[i-1].f)
sf[++m] = v[i].f;
}
int dr = 0;
for(int i = 1;i <= n;i ++)
{
int st = caut(v[i].s);
if(v[i].f > sf[dr])
dr ++;
dp[dr] = max(dp[dr], dp[st] + 1LL*(v[i].f - v[i].s));
dp[dr] = max(dp[dr],dp[dr-1]);
}
cout << dp[m];
return 0;
}