Cod sursa(job #1060857)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 18 decembrie 2013 20:39:17
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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(const trupa &t1, const trupa &t2)
{
    if(t1.sf==t2.sf)
    {
        return t1.inc > t2.inc;
    }
    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);
    
    for (i=2; i<=n; i++)
        cost[i]=-1;
    cost[1]=trupe[1].sf - trupe[1].inc;
    for (i=2; i<=n; i++)
    {
        st=1;
        dr=i;
        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);
                if(Max < cost[i])
                    Max=cost[i];
                st=mij+1;
            }
            else
                dr=mij-1;
        }
    }
    g<<Max;
    return 0;
}