Cod sursa(job #1335852)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 5 februarie 2015 23:14:31
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.98 kb
#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;
}