Cod sursa(job #2367675)

Utilizator DianaVelciovVelciov Diana DianaVelciov Data 5 martie 2019 11:54:20
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

const int NMax = 1e5 + 2;
int N, DP[NMax];

struct Concert{
    int TStart, TFinnish, Len;
};
Concert C[NMax];

bool Compare(Concert A, Concert B){
    if (A.TFinnish == B.TFinnish)
        return A.TStart < B.TStart;
    return A.TFinnish < B.TFinnish;
}

void Read(){
    in >> N;
    for (int i = 1; i <= N; ++i){
        in >> C[i].TStart >> C[i].TFinnish;
        C[i].Len = C[i].TFinnish - C[i].TStart;
    }
    sort(C, C + N + 1, Compare);
}

void Solve(){
    for (int i = 1; i <= N; ++i){
        int Last = C[i-1].TFinnish;
        int k = 1;
        while (Last < C[i].TStart && i - k){
            k++;
            Last = C[i-k].TFinnish;
        }
        DP[i] = max(DP[i-1], DP[i-k] + C[i].Len);
    }
}

int main(){
    Read();
    Solve();
    out << DP[N];
    return 0;
}