Cod sursa(job #2893963)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 26 aprilie 2022 22:20:18
Problema Heavy metal Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <algorithm>
#include <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];

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);
}