Cod sursa(job #3239597)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 6 august 2024 20:07:12
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
    
    int N, i, j, ma, l, r, bun, md;
    fin >> N;

    pair<int, int> ore[N];
    // m[i] = maximul de ore de program ce se pot planifica din primele i concerte
    int m[N];
    
    for(i=0; i<N; ++i) {
        fin >> ore[i].first >> ore[i].second;
    }
    
    // Ordonare după al doilea element, adică ora de sfârșit
    sort(ore, ore+N, [](const std::pair<int, int> &left, const std::pair<int, int> &right) {
        return left.second < right.second;
    });

    // Cazul de bază: dintr-un singur concert, putem alege doar să-l programăm
    m[0] = ore[0].second - ore[0].first;

    for(i=1; i<N; ++i) {
        ma = ore[i].second - ore[i].first;
        l = 0;
        r = i-1;
        bun = -1;

        while(l<=r) {
            md = l + (r-l) / 2;
            if(ore[md].second <= ore[i].first) {
                bun = md;
                l = md+1;
            } else {
                r = md-1;
            }
        }

        if(bun != -1) {
            ma += m[bun];
        }

        // Alegem dacă adăugăm noul concert sau nu
        m[i] = max(ma, m[i-1]);
    }

    fout << m[N-1];

    return 0;
}