Pagini recente » Cod sursa (job #1829220) | Cod sursa (job #140451) | Cod sursa (job #2775916) | Cod sursa (job #1586453) | Cod sursa (job #2498009)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct formatie{
int a,b;
};
const int inf = 1000000003;
formatie f[100004];
int DP[100004];
int DPstart[100004];
bool cmp(formatie x,formatie y){
if(x.b < y.b){
return 1;
}else{
return 0;
}
}
//bool binsrc(int )
int main()
{
int n,i,aux,j,durata;
fin>>n;
for(i = 1; i <= n ; i++){
fin>>f[i].a>>f[i].b;
}
sort(f+1,f+n+1,cmp);
for(i = 1; i <= n; i++){
aux = 0;
j = i-1;
durata = f[i].b - f[i].a;
while(!aux && j){
if(DPstart[j] <= f[i].a){
aux = DP[j];
}
j--;
}
if(DP[i-1] < aux + durata){
DP[i] = aux + durata;
DPstart[i] = f[i].b;
}else{
DP[i] = DP[i-1];
DPstart[i] = DPstart[i-1];
}
}
fout<<DP[n]<<endl;
return 0;
}