Cod sursa(job #3201466)

Utilizator thinkphpAdrian Statescu thinkphp Data 8 februarie 2024 14:00:42
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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);
}

int binarysearch(int Val, int End) {
    int lo = 1, hi = End, Sol = -1;
    while (lo <= hi) {
        int mid = (lo+hi) / 2;
        if (V[mid].B <= Val)
            Sol = mid,lo = mid + 1;
        else
            hi = mid - 1;
    }
    return Sol;
}

void Solve() {
    for (int i = 1; i <= N; i++) {
        DP[i] = max(DP[binarysearch(V[i].A,i-1)] + V[i].len, DP[i-1]);
    }

    out << DP[N];
}

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