Pagini recente » Cod sursa (job #1742016) | Cod sursa (job #2103618) | Cod sursa (job #2085097) | Cod sursa (job #2174234) | Cod sursa (job #2919260)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct show{
int s, f;
};
int n, dmax;
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=0;
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);
}
for(int i=1;i<=n;i++)
dmax=max(dmax, dp[i]);
fout<<dmax;
return 0;
}