Pagini recente » Cod sursa (job #3189324) | Cod sursa (job #623451) | Cod sursa (job #3235219) | Cod sursa (job #300403) | Cod sursa (job #2751199)
#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;
}