Pagini recente » Cod sursa (job #2959310) | Cod sursa (job #734410) | Cod sursa (job #1493472) | Cod sursa (job #2394195) | Cod sursa (job #2367675)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int NMax = 1e5 + 2;
int N, DP[NMax];
struct Concert{
int TStart, TFinnish, Len;
};
Concert C[NMax];
bool Compare(Concert A, Concert B){
if (A.TFinnish == B.TFinnish)
return A.TStart < B.TStart;
return A.TFinnish < B.TFinnish;
}
void Read(){
in >> N;
for (int i = 1; i <= N; ++i){
in >> C[i].TStart >> C[i].TFinnish;
C[i].Len = C[i].TFinnish - C[i].TStart;
}
sort(C, C + N + 1, Compare);
}
void Solve(){
for (int i = 1; i <= N; ++i){
int Last = C[i-1].TFinnish;
int k = 1;
while (Last < C[i].TStart && i - k){
k++;
Last = C[i-k].TFinnish;
}
DP[i] = max(DP[i-1], DP[i-k] + C[i].Len);
}
}
int main(){
Read();
Solve();
out << DP[N];
return 0;
}