Cod sursa(job #2751199)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 14 mai 2021 15:57:52
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define NMAX 100000

using namespace std;

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

//int best[NMAX + 1];
int bestTotal[NMAX + 1];

struct formatie{
    int a, b;
}v[NMAX + 1];

int comparare(formatie X, formatie Y){
    return X.b < Y.b; //la egalitate nu ma intereseaza ce se intampla
}

int main()
{
    int N;
    fin >> N;

    for(int i = 1; i <= N; i++){
        fin >> v[i].a >> v[i].b;
    }

    sort(v + 1, v + N + 1, comparare);

    for(int i = 1; i <= N; i++){
        //il caut binar pe primul din stanga lui i care se termina inainte sau in acelasi timp sa inceapa i
        int left = 0;
        int right = i;

        while(right - left > 1){
            int mid = left + (right - left) / 2;

            if(v[mid].b <= v[i].a){
                left = mid;
            }
            else {
                right = mid;
            }
        }

        //raspunsul se afla in left
        int candidat = bestTotal[left] + (v[i].b - v[i].a); //de fapt, candidat = best[i], unde best[i] inseamna cel mai bun rezultat cand totul se termina in i

        bestTotal[i] = max(bestTotal[i - 1], candidat);
    }

    fout << bestTotal[N];
    return 0;
}