Cod sursa(job #3239586)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 6 august 2024 18:45:13
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int main() {
    ifstream fin("heavymetal.in");
    ofstream fout("heavymetal.out");
    
    unsigned int N, i, j, ma;
    fin >> N;
    pair<unsigned int, unsigned int> ore[N];
    unsigned int m[N]={};
    for(i=0; i<N; ++i) {
        fin >> ore[i].first >> ore[i].second;
    }
    sort(ore, ore+N, [](const std::pair<unsigned int, unsigned int> &left, const std::pair<unsigned int,unsigned int> &right) {
        return left.second < right.second;
    });

    m[0] = ore[0].second - ore[0].first;

    for(i=1; i<N; ++i) {
        ma = ore[i].second - ore[i].first;
        for(j=i-1; j>=0; --j) {
            if(ore[j].second <= ore[i].first) {
                ma += m[j];
                break;
            }
        }

        m[i] = max(ma, m[i-1]);
    }

    fout << m[N-1];

    return 0;
}