Cod sursa(job #1850137)

Utilizator stanciuandreiStanciulescu Andrei stanciuandrei Data 18 ianuarie 2017 11:16:47
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define M_LEN 100000

using namespace std;

struct Concert{
    int start, fin, len;
};

bool sortRule(Concert a, Concert b){
    if(a.start<b.start)
        return 1;
    if(a.start>b.start)
        return 0;
    return a.fin>b.fin;
}

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

Concert concerte[M_LEN];
int dinamic[M_LEN];

int n;

int main()
{
    in>>n;
    for(int i=0;i<n;i++){
        in>>concerte[i].start>>concerte[i].fin;
        concerte[i].len = concerte[i].fin - concerte[i].start;
    }
    sort(concerte, concerte+n, sortRule);
    dinamic[0] = concerte[0].len;
    for(int i=1;i<n;i++){
        dinamic[i] = concerte[i].len;
        for(int j=i-1;j>=0;j--){
            if(concerte[i].start>=concerte[j].fin && dinamic[j] + concerte[i].len > dinamic[i])
                dinamic[i] = dinamic[j] + concerte[i].len;
        }
    }
    out<<dinamic[n-1]<<'\n';
    return 0;
}