Pagini recente » Cod sursa (job #2582525) | Cod sursa (job #1203518) | Cod sursa (job #220306) | Cod sursa (job #63587) | Cod sursa (job #2919258)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct show{
int s, f;
};
int n, nrs;
int dp[100000];
show v[100001];
bool comp( show A, show B){
return A.f<B.f;
}
int main(){
fin>>n;
for(int i=1;i<=n;i++){
fin>>v[i].s;
fin>>v[i].f;
}
sort(v+1, v+n+1, comp);
for(int i=1;i<=n;i++){
int st=1, dr=i, mij, p=-1;
int x=v[i].s;
while(st<=dr){
mij=(st+dr)/2;
if(v[mij].f<=x){
if(mij>p)
p=mij;
st=mij+1;
}
else dr=mij-1;
}
dp[i]=dp[p]+(v[i].f-v[i].s);
}
fout<<dp[n];
return 0;
}