Pagini recente » Cod sursa (job #2222448) | Cod sursa (job #2018629) | Cod sursa (job #1329749) | Cod sursa (job #2045368) | Cod sursa (job #1335852)
#include <fstream>
#include <algorithm>
#define DIM 100010
#define f first
#define s second
using namespace std;
ifstream fin ("date.in" );
ofstream fout("date.out");
int n, m, i, j, k, ok, minim;
pair <int , int> v[DIM], w[DIM];
int t[DIM*2], q[DIM*2], g[DIM];
int mid, aux, maxim, val, h, z[DIM];
int CautBin(int p, int u, int val,int h){
if(h == 1){
while(p <= u){
mid = (p+u)/2;
if(t[mid] == val)
return q[mid];
if(t[mid] < val)
p = mid + 1;
else
u = mid - 1;
}
}
if(h == 2){
while(p <= u){
mid = (p+u)/2;
if(w[mid].f <= val)
p = mid + 1;
else
u = mid - 1;
}
return u;
}
}
void SetUpNormal(){
fin >> n;
for(i = 1; i <= n; i ++){
fin >> v[i].s >> v[i].f;
t[i*2-1] = v[i].s; t[i*2] = 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;
}
for(i = 1; i <= n; i ++)
z[i] = v[i].s - v[i].f;
sort(t + 1, t + n*2 + 1);
for(i = 1; i <= n*2; i ++)
if(t[i] == t[i-1])
q[i] = q[i-1] + 0;
else
q[i] = q[i-1] + 1;
for(i = 1; i <= n; i ++){
v[i].f = CautBin(1, n*2, v[i].f, 1);
v[i].s = CautBin(1, n*2, v[i].s, 1);
}//BUN...DECI AM NORMALIZAT
return;
}
void DinamycGredy(){
w[1].f = v[1].s; maxim = g[v[1].s];
w[1].s = v[1].s - v[1].f;
g[v[1].s] = z[1];
for(i = 2; i <= n; i ++){
w[i].f = v[i].s;
val = CautBin(1, i, v[i].f, 2);
//val = linia cu maximul;
g[v[i].s] = max(g[v[i].s], g[v[val].s] + z[i]);
if(maxim < g[v[i].s])
maxim = g[v[i].s];
}
fout << maxim;
return;
}
int main(){
SetUpNormal();
DinamycGredy();
return 0;
}