Cod sursa(job #1744633)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 20 august 2016 01:28:36
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");

int dp[100010];
pair<int, int> v[100010];

bool Compare(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}

int BinarySearch(int left, int right, int value) {
    int answer = -1;
    while (left <= right) {
        int middle = (left + right) / 2;
        if (v[middle].second <= value) {
            answer = middle;
            left = middle + 1;
        }
        else
            right = middle - 1;
    }
    return answer;
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1, Compare);
    for (int i = 1; i <= n; i++) {
        int j = BinarySearch(1, n, v[i].first);
        dp[i] = max(dp[i - 1], dp[j] + v[i].second - v[i].first);
    }
    cout << dp[n];
    return 0;
}