Cod sursa(job #1207050)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 11 iulie 2014 22:14:39
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#include <algorithm>

using namespace std;

struct BAND
{
    int left;
    int right;
};

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

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

bool SortRight(BAND A, BAND B)
{
    if(A.right == B.right) return A.left > B.left;
    return A.right < B.right;
}

int main()
{
    FILE *in = fopen("heavymetal.in", "r");
    FILE *out = fopen("heavymetal.out", "w");

    int i, pos, x, y;

    fscanf(in, "%d", &N);
    for(i=1; i<=N; i++)
    {
         fscanf(in, "%d %d", &x, &y);
         bands[i].left = x;
         bands[i].right = y;
    }

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