Pagini recente » Cod sursa (job #2444326) | Cod sursa (job #1433434) | Cod sursa (job #2482162) | Cod sursa (job #2307529) | Cod sursa (job #1751821)
#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<unordered_set>
#include<set>
#include<math.h>
using namespace std;
int n, dp[100100], i, a, b, val,el,prvval,j,anteval,ok,max1;
vector<pair<int, int>>v[100010];
vector<pair<int, int>>::iterator it;
int main()
{
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
f >> n;
for (i = 1; i <= n; i++)
{
f >> a >> b;
v[i].push_back(make_pair(a, b));
}
sort(v + 1, v + n + 1);
max1 = -1;
for (j = 1; j <= n; j++)
{
i = v[j].begin()->first;
ok = 0;
if (i != v[j].begin()->second)
{
if (dp[i] == 0)
dp[i] = prvval;
else
{
dp[i] = max(prvval, dp[i]);
}
i++;
}
while (i != v[j].begin()->second)
{
if (dp[i] == 0)
dp[i] = prvval;
else
{
dp[i] = max(anteval, dp[i]);
ok = 1;
}
i++;
}
if(!ok)
dp[i] = v[j].begin()->second - v[j].begin()->first+prvval;
else
dp[i] = v[j].begin()->second - v[j].begin()->first + anteval;
if (max1 < dp[i])
max1 = dp[i];
el = anteval;
anteval = prvval;
if (!ok)
prvval = prvval + v[j].begin()->second - v[j].begin()->first;
else
prvval = el + v[j].begin()->second - v[j].begin()->first;
}
g << max1;
return 0;
}