Cod sursa(job #1206411)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 9 iulie 2014 21:00:00
Problema Heavy metal Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MaxBAND 2000

struct Band
{
    int left;
    int right;
    int l;
} band;
vector<Band> bands;
int best[3800000];

bool sort_right(Band a, Band b)
{
    return a.right < b.right;
}

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

    int n, i, val, cpy, j, k, maxx=0;

    scanf("%d", &n);
    for(i=0; i<n; i++)
    {
        scanf("%d %d", &band.left, &band.right);
        maxx = max(maxx,band.right);
        band.l = band.right - band.left;
        bands.push_back(band);
    }
    sort(bands.begin(), bands.end(), sort_right);
    best[bands[0].right] = bands[0].l;
    for(i=1; i<=maxx; i++)
    {
        best[i] = best[i-1];
        for(j=0; j<bands.size() && bands[j].right < i; j++);
        for(; bands[j].right == i; j++)
        {
            best[i] = max(best[i], best[bands[j].left] + bands[j].right - bands[j].left);
        }
    }
    printf("%d", best[maxx]);
    return 0;
}