Pagini recente » Cod sursa (job #1232170) | Cod sursa (job #460967) | Cod sursa (job #479914) | Istoria paginii runda/sim3333/clasament | Cod sursa (job #1939414)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct spectacol{
int inceput, sfarsit;
};
int N;
vector <spectacol> V;
vector <int> DP;
bool cmp(spectacol a, spectacol b){
return a.sfarsit < b.sfarsit;
}
void Read(){
spectacol aux;
in >> N;
for(int i = 1; i <= N; ++i){
in >> aux.inceput >> aux.sfarsit;
V.push_back(aux);
}
sort(V.begin(), V.end(), cmp);
}
int BinarySearch(int poz){
int left = 0;
int right = poz;
int mid, sol = 0;
while(left <= right){
mid = (left + right) / 2;
if(V[mid].sfarsit <= V[poz].inceput){
sol = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return sol;
}
void SolveAndPrint(){
DP.push_back(V[0].sfarsit - V[0].inceput);
for(int i = 1; i < N; ++i){
int best = BinarySearch(i);
DP.push_back(max((V[i].sfarsit - V[i].inceput) + DP[best], DP[i - 1]));
}
out << DP[N - 1] << "\n";
}
int main(){
Read();
SolveAndPrint();
return 0;
}