Cod sursa(job #1061360)

Utilizator dorupopDoru Pop dorupop Data 19 decembrie 2013 17:18:20
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 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]=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;
        }
    }
    g<<cost[n];
    return 0;
}