Cod sursa(job #762052)

Utilizator informatician28Andrei Dinu informatician28 Data 28 iunie 2012 15:13:55
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <algorithm>
#define DIM 100001
#define INF 0x3f3f3f3f

using namespace std;

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

int N;
long long best[DIM], maxim;  // durata maxima ce se poate obtine pana la spectacolul i
struct show
{
   int start, end, dif;
}s[DIM];

bool comp(const show &unu, const show &doi)
{
    return (unu.start < doi.start) || unu.end < doi.end;
}

int main()
{
    int i, j;

    in >> N;
    for(i = 1; i <= N; i++)
    {
        in >> s[i].start >> s[i].end;
        s[i].dif = s[i].end - s[i].start;
    }
    sort(s+1, s+N+1, comp);
    best[1] = s[1].dif;
    for(i = 2; i <= N; i++)
    {
        maxim = -INF;
        for(j = 1; j < i; j++)
        {
            if( s[i].start >= s[j].end )
            {
                if( best[j] > maxim )
                {
                    maxim = best[j];
                }
            }
        }
        best[i] = s[i].dif + maxim;
    }
    maxim = -INF;
    for(i = 1; i <= N; i++)
    {
        if( best[i] > maxim )
        {
            maxim = best[i];
        }
    }
    out << maxim;
    return 0;
}