Cod sursa(job #2346066)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 17 februarie 2019 00:22:39
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>

std::istream& operator >> (std::istream& stream, std::pair <int, int>& data) {
    return stream >> data.first >> data.second;
}

bool cmp(const std::pair <int, int>& pair, const std::pair <int, int>& other) {
    if (pair.second == other.second)
        return pair.first < other.first;
    return pair.second < other.second;
}

#define int_pair std::pair <int, int>

#define MAXN 100005

int N, DP[MAXN];
int_pair V[MAXN];

std::ifstream In ("heavymetal.in");
std::ofstream Out("heavymetal.out");

void Citire() {
    In >> N;
    for (int i=1; i<=N; ++i)
        In >> V[i];
}

void Rezolvare() {
    std::sort(V+1, V+N+1, cmp);

    for (int i=1, lbound, rbound, mid, ans; i<=N; ++i) {
        DP[i] = std::max(DP[i-1], V[i].second - V[i].first);

        lbound = 1, rbound = i-1, ans = 0;
        while (lbound <= rbound) {
            mid = (lbound + rbound)/2;
            if (V[mid].second <= V[i].first)
                ans = mid, lbound = mid+1;
            else
                rbound = mid-1;
        }

        if (ans)
            DP[i] = std::max(DP[i], DP[ans] + V[i].second - V[i].first);
    }   Out << DP[N] << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}