Cod sursa(job #2511684)

Utilizator cyber_ghSoltan Gheorghe cyber_gh Data 19 decembrie 2019 16:40:56
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair<int64_t,int64_t> pii;
const int64_t MAXN = 1000010;

int64_t N;
int64_t dp[MAXN];
vector<pii> arr;
int main(){

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

    fin >> N;

    arr.resize(N);
    for (int64_t i = 0; i < N; i++)
        fin >> arr[i].first >> arr[i].second;


    sort(arr.begin(), arr.end(), [](const pii &a, const pii &b) {
            return a.second < b.second;
    });

    dp[0] = arr[0].second - arr[0].first;
    int64_t ans = 0;
    for (int64_t i = 1; i < N; i++) {
        int64_t mx = 0;

        int64_t left = 0, right = i - 1, ans = left - 1;
            while (left <= right) {
                int64_t mid = (left + right) / 2;
                if (arr[mid].second <= arr[i].first) {
                    ans = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

        if (ans >= 0) {
            mx = dp[ans];
        }

        dp[i] = max(dp[i - 1], mx + arr[i].second - arr[i].first);
    }

    fout << dp[N - 1];
    return 0;
}