Pagini recente » Istoria paginii runda/knird/clasament | Cod sursa (job #652079) | Cod sursa (job #1764037) | Cod sursa (job #209469) | Cod sursa (job #1752691)
#include <fstream>
#include <algorithm>
#define f first
#define s second
using namespace std;
int n,i,best[100001],p,u,m,aux;
pair <int,int> 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] = i;
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;
}