Pagini recente » Cod sursa (job #1313294) | Cod sursa (job #2673395) | Cod sursa (job #1817575) | Cod sursa (job #2270586) | Cod sursa (job #1117183)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
struct Event{
int begining, ending;
};
#define NMAX 10010
int N,Maximum,DP[NMAX];
Event Events[NMAX];
bool cmp(Event A,Event B) {
return A.ending < B.ending;
}
void Read(){
f>>N;
for (int i = 1; i <= N; i++) {
f>>Events[i].begining>>Events[i].ending;
}
}
int Search(int point)
{
int left = 0,right = point ,middle;
while (left <= right) {
middle = (left + right)/2;
if (Events[middle].ending > Events[point].begining) {
right = middle - 1;
}else{
left = middle + 1;
}
}
return (left+right)/2;
}
void Solve(){
sort(Events+1, Events+N+1, cmp);
DP[1] = Events[1].ending - Events[1].begining;
Maximum = DP[1];
int position,value;
for (int i = 2; i <= N; i++) {
position = Search(i);
value = Events[i].ending - Events[i].begining;
if (DP[position] + value > Maximum) {
Maximum = DP[position] + value;
}
DP[i] = Maximum;
}
}
void Write(){
g<<Maximum;
}
int main()
{
Read();
Solve();
Write();
return 0;
}