Cod sursa(job #2719384)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 9 martie 2021 20:06:05
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

#define NMAX 100005
using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

struct data{
    int x, y;
}v[NMAX];

inline bool cmp(data a, data b){
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

int dp[NMAX];

int main()
{
    int n;
    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){
        int st = 1;
        int dr = i - 1;
        int best = 0;
        while(st <= dr){
            int mij = (st + dr) / 2;
            if(v[mij].y <= v[i].x){
                best = mij;
                st = mij + 1;
            }
            else dr = mij - 1;
        }

        dp[i] = max(dp[i - 1], dp[best] + v[i].y - v[i].x);
    }
    fout << dp[n] << '\n';
    return 0;
}