Pagini recente » Cod sursa (job #2988469) | Cod sursa (job #2568595) | Cod sursa (job #1864413) | Cod sursa (job #2049115) | Cod sursa (job #1521463)
#include <bits/stdc++.h>
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define mod 666013
using namespace std;
struct formatie
{
int st, dr, val;
}v[100005];
int n, i, j, x, mx, sol;
int dp[200005];
vector <int> a;
unordered_map <int, int> mp;
bool cmp(formatie a, formatie b)
{
if(a.st == b.st)
return a.dr < b.dr;
return a.st < b.st;
}
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &n);
for(i = 1; i <= n; i++)
{
scanf("%d%d", &v[i].st, &v[i].dr);
a.push_back(v[i].st);
a.push_back(v[i].dr);
v[i].val = v[i].dr - v[i].st;
}
sort(a.begin(), a.end());
x = 0;
for(i = 0; i < a.size(); i++)
{
if(mp.count(a[i]))
continue;
mp[ a[i] ] = ++x;
}
for(i = 1; i <= n; i++)
{
v[i].st = mp[ v[i].st ];
v[i].dr = mp[ v[i].dr ];
}
sort(v + 1, v + n + 1, cmp);
mx = 0;
j = 0;
for(i = 1; i <= n; i++)
{
while(j < v[i].st)
{
j++;
mx = max(mx, dp[j]);
}
dp[ v[i].dr ] = max(dp[ v[i].dr ], mx + v[i].val);
sol = max(sol, dp[ v[i].dr ]);
}
printf("%d", sol);
return 0;
}