Pagini recente » Cod sursa (job #2285485) | Clasament pbb | Cod sursa (job #261853) | Clasament rezolvarijudeteanaliceu | Cod sursa (job #2497997)
#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 j = i;
do{
j--;
}while(T[j].final >= T[i].start);
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;
}