Pagini recente » Cod sursa (job #1370902) | Cod sursa (job #1975003) | Cod sursa (job #107996) | Cod sursa (job #2249830) | Cod sursa (job #3239597)
#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;
}