Pagini recente » Cod sursa (job #2208151) | Cod sursa (job #2486808) | Cod sursa (job #2028448) | Cod sursa (job #980918) | Cod sursa (job #1851878)
#include <iostream>
#include <fstream>
#include <algorithm>
#define M_LEN 100000
using namespace std;
struct Concert{
int start, fin, len;
};
bool sortRule(Concert a, Concert b){
if(a.start<b.start)
return 1;
if(a.start>b.start)
return 0;
return a.fin>b.fin;
}
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
Concert concerte[M_LEN];
int dinamic[M_LEN];
int n;
int main()
{
in>>n;
for(int i=0;i<n;i++){
in>>concerte[i].start>>concerte[i].fin;
concerte[i].len = concerte[i].fin - concerte[i].start;
}
sort(concerte, concerte+n, sortRule);
dinamic[0] = concerte[0].len;
for(int i=1;i<n;i++){
dinamic[i] = concerte[i].len;
for(int j=i-1;j>=0;j--){
if(concerte[i].start>=concerte[j].fin && dinamic[j] + concerte[i].len > dinamic[i])
dinamic[i] = dinamic[j] + concerte[i].len;
}
}
out<<dinamic[n-1]<<'\n';
return 0;
}