Cod sursa(job #1061372)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 19 decembrie 2013 17:28:49
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("heavymetal.in");
ofstream g("heavymetal.out");

struct trupa
{
    int inc, sf;
}trupe[100001];

bool compara( trupa t1,  trupa t2)
{
    
    return t1.sf < t2.sf;
}

int n, i, j, dr, st, mij, sol, cost[100001], Max=-1;
int main()
{
    f>>n;
    for (i=1; i<=n; i++)
    {
        f>>trupe[i].inc>>trupe[i].sf;
    }
    sort(trupe + 1, trupe + n + 1, compara);
    
    cost[1]=trupe[1].sf-trupe[1].inc;
    Max=cost[1];
    for (i=2; i<=n; i++)
    {
        st=1;
        dr=i-1;
        //cost[i] se initializeaza cu cost[i-1]  in cazul in care este mai mare decat trupe[i].sf-trup[i].inc; altfel nu merge cautarea binara; intervalul i poate sa nu participe la solutie dar
        // tu preiei valoarea din intervalul anterior
        cost[i]=max(cost[i-1],trupe[i].sf-trupe[i].inc);
        while (st<=dr)
        {
            mij=(st+dr)/2;
            if (trupe[i].inc >=  trupe[mij].sf)
            {
                cost[i]=max(cost[i], cost[mij] + trupe[i].sf - trupe[i].inc);
                
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        if(Max<cost[i])
            Max=cost[i];
    }
    g<<Max;
    return 0;
}