Pagini recente » Cod sursa (job #1534086) | Cod sursa (job #2810432) | Cod sursa (job #2155736) | Cod sursa (job #2611766) | Cod sursa (job #2498020)
#include <iostream>
#include <fstream>
#include <algorithm>
#define final first
#define start second
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int DP[100005], f, s;
pair <int, int> T[100005];
int n;
void Read(){
fin>>n;
for(int i = 1; i <= n; i++){
fin>>T[i].start>>T[i].final;
}
sort(T+1, T+1+n);
}
void Solve(){
int Max = 0;
for(int i = 1; i <= n; i++){
if(f <= T[i].start){
DP[i] = DP[i-1] + T[i].final - T[i].start;
}
else{
int k = i;
do{
k--;
}while(T[k].final >= T[i].start);
for(int j = k; j > 0; j--)
DP[i] = max(DP[i],DP[j] + T[i].final - T[i].start);
}
f = T[i].final;
if(DP[i] > Max) Max = DP[i];
}
fout<<Max;
}
int main()
{
Read();
Solve();
return 0;
}