Cod sursa(job #2553902)

Utilizator AnastasiaStefanescuAnastasia Stefanescu AnastasiaStefanescu Data 22 februarie 2020 13:04:48
Problema Heavy metal Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <algorithm>
#include <fstream>
using namespace std;

ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");

struct intervale{
    int inc, sf;
}it[100001];

int n, maxime_partiale[100001];

int cautare_binara_st(int ind)
{
    int st, dr, mijl, p;
    st = 1;
    dr = ind-1;
    p = 0;
    while (st<= dr)
    {
        mijl = (st + dr)/2;
        if (it[mijl].sf < it[ind].inc)
        {
            p = mijl;
            st = mijl+1;
        }
        else
        {
            if(it[mijl].sf == it[ind].inc)
                return mijl;
            else
            {
                if(it[mijl].sf > it[ind].inc)
                    dr = mijl-1;
            }
        }
    }
    return p;
}


int conditie(intervale el1, intervale el2)
{
//    if(el1.sf > el2.sf)
//        return el1 > el2;
//    if(el1.sf == el2.sf)
//    {
//        if(el1.inc > el2.inc)
//            return el2 > el1;
//        return el1 > el2;
//    }
    return el1.sf < el2.sf;
}

int main()
{
    int i, p;
    fin >> n;
    for (i= 1; i<= n; i++)
        fin >> it[i].inc >> it[i].sf;
    
    //sortam intervalele crescator dupa sfarsituri
    sort(it + 1, it+n+1, conditie);
    
    for(i = 1; i<= n; i++)
    {
        p = -1;
        p = cautare_binara_st(i);
        if(maxime_partiale[p] + (it[i].sf - it[i].inc) > maxime_partiale[i-1])
            maxime_partiale[i] = maxime_partiale[p] + (it[i].sf - it[i].inc);
        else
            maxime_partiale[i] = maxime_partiale[i-1];
    }
    
    fout << maxime_partiale[n];
    
    
    
        return 0;
}