Cod sursa(job #2774124)

Utilizator DragosC1Dragos DragosC1 Data 9 septembrie 2021 19:25:15
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <algorithm>
using namespace std;
 
int n;
pair<int, int> a[100001];

void read() {
    int i;
    ifstream f("heavymetal.in");
    f >> n;
    for (i = 1; i <= n; i++)
        f >> a[i].first >> a[i].second;
    f.close();
}

bool csort(pair<int, int> a, pair<int, int> b) {
    if (a.second < b.second)
        return 1;
    else if (a.second == b.second && a.first < b.first)
        return 1;
    return 0;
}

const int Inf = -1e9 - 100;
int dp[100001];

void solve() {
    int x, y, st, dr, mij;
    sort(a + 1, a + n + 1, csort);
    int i;
    dp[0] = 0;
    for (i = 1; i <= n; i++)
        dp[i] = -Inf;
    for (i = 1; i <= n; i++) {
        x = a[i].first, y = a[i].second;
        st = 1, dr = i - 1;
        while (st <= dr) {
            mij = (st + dr) / 2;
            if (a[mij].second <= x) 
                st = mij + 1;
            else dr = mij - 1;
        }
        dp[i] = max(dp[i - 1], dp[dr] + (y - x));
    }
}

void output() {
    ofstream g("heavymetal.out");
    g << dp[n];
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}