Cod sursa(job #2497989)

Utilizator Dragos1226Dragos Chileban Dragos1226 Data 23 noiembrie 2019 13:15:10
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.77 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
const int NMax = 100000;
int N, A[NMax+5], B[NMax+5], DP[NMax+5];

struct heavy {
    int A, B, len;
}V[NMax+5];

bool cmp(heavy x, heavy y) {
    return x.B < y.B;
}

void Read() {
    in >> N;
    for (int i = 1; i <= N; i++) {
        in >> V[i].A >> V[i].B;
        V[i].len = V[i].B - V[i].A;
    }
    sort(V+1, V+N+1, cmp);
}

void Solve() {
    for (int i = 1; i <= N; i++) {
        for (int j = i-1; j >= 1; j--)
            if(V[i].A >= V[j].B)
                DP[i] = DP[j] + V[i].len, j=0;
        if (!DP[i])
        DP[i] = max(V[i].len, DP[i-1]);
    }

    out << DP[N];
}

int main() {
    Read();
    Solve();
}