Cod sursa(job #1207030)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 11 iulie 2014 21:03:50
Problema Heavy metal Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct BAND
{
    int left;
    int right;
};

BAND bands[10001];
int best[10001], N;

int BinSearch(int POS)
{
    int Begin, End, Mid, Closest;
    Begin = 0; End = N;
    while(Begin <= End)
    {
        Mid = (Begin+End)/2;
        if(bands[Mid].right < bands[POS].left)
        {
            Closest = Mid;
            Begin = Mid+1;
        }
        if(bands[Mid].right > bands[POS].left) End = Mid-1;
        if(bands[Mid].right == bands[POS].left) return Mid;
    }
    return Closest;
}

bool SortRight(BAND A, BAND B) { return A.right < B.right; }

int main()
{
    freopen("heavymetal.in", "r", stdin);
    freopen("heavymetal.out", "w", stdout);

    int i, j, pos;

    scanf("%d", &N);
    for(i=1; i<=N; i++) scanf("%d %d", &bands[i].left, &bands[i].right);

    sort(&bands[1], &bands[N+1], SortRight);
    for(i=1; i<=N; i++)
    {
        best[i] = best[i-1];
        pos = BinSearch(i);
        best[i] = max(best[i], best[pos] + bands[i].right - bands[i].left);
    }
    printf("%d\n", best[N]);
    return 0;
}