Pagini recente » Cod sursa (job #2506887) | Cod sursa (job #1310893) | Cod sursa (job #1396491) | Cod sursa (job #1093351) | Cod sursa (job #2135784)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct Band{
int begin, end;
Band(int b, int e){
begin = b;
end = e;
}
bool const operator<(const Band &other)const{
return end < other.end;
}
};
const int NMAX = 100005;
int N;
int DP[NMAX];
vector <Band> V;
void Read(){
in >> N;
for(int i = 1; i <= N; ++i){
int a, b;
in >> a >> b;
V.push_back(Band(a, b));
}
sort(V.begin(), V.end());
}
int BinarySearch(int poz){
int sol = 0;
int left = 0, right = N + 5;
while(left <= right){
int mid = (left + right) / 2;
if(mid < N && V[mid].end <= V[poz].begin){
sol = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return sol;
}
void SolveAndPrint(){
DP[0] = (V[0].end - V[0].begin);
for(int i = 1; i < N; ++i){
int best = BinarySearch(i);
DP[i] = max((V[i].end - V[i].begin) + DP[best], DP[i - 1]);
}
out << DP[N - 1] << "\n";
}
int main(){
Read();
SolveAndPrint();
return 0;
}