Pagini recente » Cod sursa (job #2652521) | Cod sursa (job #3160805) | Cod sursa (job #1766461) | Cod sursa (job #1401090) | Cod sursa (job #2445927)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, best[100005], maxx[100005], maxim_local, maxim;
struct Interval
{
int x, y;
}v[100005];
bool cmp(Interval a, Interval b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
int cautbin(int i)
{
int st = 1, dr = i - 1, sol = -1;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (v[mid].y <= v[i].x)
{
sol = mid;
st = mid + 1;
}
else
{
dr = mid - 1;
}
}
return sol;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
for (int i = 1; i <= n; ++i)
best[i] = v[i].y - v[i].x;
maxx[1] = best[1];
for (int i = 2; i <= n; ++i)
{
int sol = cautbin(i);
maxim_local = 0;
if (sol > 0)
maxim_local = maxx[sol];
if (maxim_local > 0) best[i] = best[i] + maxim_local;
maxim = max(maxim, best[i]);
maxx[i] = max(maxx[i - 1], best[i]);
}
fout << maxim;
}