Pagini recente » Cod sursa (job #1661652) | Cod sursa (job #287567) | Cod sursa (job #2235051) | Cod sursa (job #1514418) | Cod sursa (job #1335855)
#include <fstream>
#include <algorithm>
#define DIM 100010
#define l first
#define r second
using namespace std;
ifstream fin ("heavymetal.in" );
ofstream fout("heavymetal.out");
long long n, m, i, j, k, ok, minim, aux, best[DIM];
pair <int , int > v[DIM]; long long a, b, mid;
long long max(long long a, long long b){
if(a > b)
return a;
else
return b;
}
void SetUpNormal(){
fin >> n;
for(i = 1; i <= n; i ++)
fin >> v[i].r >> v[i].l;
sort(v + 1, v + n + 1);
for(i = 1; i <= n; i ++){
aux = v[i].l;
v[i].l = v[i].r;
v[i].r = aux;
}
return;
}
void DinamycGredy(){
best[1] = v[1].r - v[1].l;
for(i = 2; i <= n; i ++){
best[i] = best[i-1];
best[i] = max(best[i], v[i].r - v[i].l);
a = 1; b = i-1;
while(a <= b){
mid = (a+b) / 2;
if(v[mid].r <= v[i].l)
a = mid + 1;
else
b = mid - 1;
}
best[i] = max(best[i], best[b] + v[i].r - v[i].l);
}
fout << best[n];
return;
}
int main(){
SetUpNormal();
DinamycGredy();
return 0;
}