Cod sursa(job #916666)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 16 martie 2013 19:29:38
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

int n;
int best[100010];
struct concert
{
    int x, y;
};
concert a[100010];

inline void Read()
{
    ifstream f ("heavymetal.in");
    f>>n;
    int i;
    for (i=1; i<=n; i++)
        f>>a[i].x>>a[i].y;
    f.close();
}

inline bool cmp (const concert A, const concert B)
{
    return A.y < B.y;
}

inline int Cautare_Binara(int x, int dr)
{
    int rez = 0, st, mij;
    st = 1;
    while (st <= dr)
    {
        mij = (st+dr)>>1;
        if (a[mij].y <= x)
            st = mij + 1, rez = mij;
        else
            dr = mij - 1;
    }
    return rez;
}

inline void Solve()
{
    /// best[i] = intervalul de timp maxim in care pot canta concerte din intervalul [1, i]
    sort (a+1, a+n+1, cmp);
    int i, poz;
    for (i=1; i<=n; i++)
    {
        poz = Cautare_Binara(a[i].x, i-1);
        /// caut binar poz = cea mai din dreapta pozitie de inceput a concertului i care
        /// corespunde cu pozitia din best
        best[i] = max (best[i-1], best[poz] + a[i].y - a[i].x);
    }
}

inline void Write()
{
    ofstream g ("heavymetal.out");
    g<<best[n]<<"\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}