Pagini recente » Cod sursa (job #2011424) | Cod sursa (job #2893152) | Cod sursa (job #2009259) | Cod sursa (job #2746869) | Cod sursa (job #1752692)
#include <fstream>
#include <algorithm>
#define f first
#define s second
using namespace std;
long long n,i,best[100001],p,u,m,aux;
pair <long long,long long> v[100001];
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int main (){
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].s>>v[i].f;
sort (v+1,v+n+1);
for (i=1;i<=n;i++){
aux = v[i].f;
v[i].f = v[i].s;
v[i].s = aux;
}
best[1] = v[1].s-v[1].f;
for (i=2;i<=n;i++){
best[i] = best[i-1];
best[i] = max (best[i],v[i].s - v[i].f);
p = 1;
u = i-1;
while (p<=u){
m = (p+u)/2;
if (v[m].s <= v[i].f)
p = m+1;
else
u = m-1;
}
best[i] = max (best[i],best[u]+v[i].s-v[i].f);
}
// rezultatul ramane in best [n];
fout<<best[n];
return 0;
}