Pagini recente » Cod sursa (job #1596638) | Cod sursa (job #1472899) | Cod sursa (job #1957174) | Cod sursa (job #957650) | Cod sursa (job #1939417)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct spectacol{
int inceput, sfarsit;
};
int N;
const int NMAX = 100000;
spectacol V[NMAX];
int DP[NMAX];
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 >> V[i].inceput >> V[i].sfarsit;
sort(V + 1, V + N + 1, cmp);
}
int BinarySearch(int poz){
int left = 1;
int right = poz - 1;
int mid, sol = 1;
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[1] = V[1].sfarsit - V[1].inceput;
for(int i = 2; i <= N; ++i){
int best = BinarySearch(i);
DP[i]= max((V[i].sfarsit - V[i].inceput) + DP[best], DP[i - 1]);
}
out << DP[N] << "\n";
}
int main(){
Read();
SolveAndPrint();
return 0;
}