Cod sursa(job #2988000)

Utilizator robertanechita1Roberta Nechita robertanechita1 Data 3 martie 2023 11:47:25
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MaxN = 100005;
int n;
long long dp[MaxN];
struct Elem{
    int st, dr;
    bool operator < (const Elem A) const{
        if(dr == A.dr)
            return st < A.st;
        return dr < A.dr;
    }
}a[MaxN];

int Cb(int x){
    int mij, dr, st, p;
    st = 1; dr = n;
    p = 0;
    while(st <= dr){
        mij = (st + dr) / 2;
        if(a[mij].dr <= x){
            p = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }
    return p;
}


int main()
{
    fin >> n;
    for(int i = 1; i <= n; i++)
        fin >> a[i].st >> a[i].dr;
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        int p = Cb(a[i].st);
        dp[i] = max(dp[i - 1], dp[p] + (a[i].dr - a[i].st));
    }
    fout << dp[n] << "\n";
    return 0;
}