Cod sursa(job #2025571)

Utilizator PondorastiAlex Turcanu Pondorasti Data 22 septembrie 2017 20:56:12
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 100000;
int n, i, ans, dp[NMAX + 5], indice, st, dr, mij;
struct Alexutu {
    int x, y;
}a[NMAX + 5];
bool cmp(Alexutu a, Alexutu b) {
    return b.y > a.y;
}
int main() {
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    cin >> n;
    for(i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    sort(a + 1, a + 1 + n, cmp);
    for(i = 1; i <= n; ++i) {
        st = 1;
        dr = i;
        while (st < dr) {
            mij = (st + dr) / 2;
            if(a[mij].y <= a[i].x)
                st = mij + 1;
            else
                dr = mij;
        }
        mij = (st + dr) / 2;
        if(a[mij].y > a[i].x)
            --mij;
        dp[i] = max(dp[mij] + a[i].y - a[i].x, ans);
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return 0;
}