Pagini recente » Cod sursa (job #2851938) | Monitorul de evaluare | Cod sursa (job #956914) | Cod sursa (job #2986618) | Cod sursa (job #2893969)
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lol long long
using namespace std;
FILE *fin = fopen("heavymetal.in", "r");
FILE *fout = fopen("heavymetal.out", "w");
struct point
{
lol a, b;
};
bool f(point p1, point p2)
{
return p1.a < p2.a;
}
point p[100005];
lol points[200005];
lol dp[200005];
unordered_map<lol, int> mp;
int main()
{
int n;
fscanf(fin, "%d", &n);
points[0] = 0;
for (int i = 0; i < n; i++)
{
fscanf(fin, "%lld %lld", &p[i].a, &p[i].b);
points[2 * i + 1] = p[i].a;
points[2 * i + 2] = p[i].b;
}
sort(points, points + 2 * n + 1);
int newLen = unique(points, points + 2 * n + 1) - points;
for (int i = 0; i < newLen; i++)
mp[points[i]] = i;
sort(p, p + n, f);
lol maxx = 0;
int last = 0;
for (int i = 0; i < n; i++)
{
int req = mp[p[i].a];
while (last < req)
{
dp[last + 1] = max(dp[last + 1], dp[last]);
last++;
}
dp[mp[p[i].b]] = dp[req] + (p[i].b - p[i].a);
maxx = max(maxx, dp[mp[p[i].b]]);
}
fprintf(fout, "%lld\n", maxx);
}