Cod sursa(job #1219485)

Utilizator diana97Diana Ghinea diana97 Data 14 august 2014 12:51:28
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");

const int NMAX = 100000 + 1;
int n;
int sol[NMAX];
pair <int, int> v[NMAX];

void citeste () {
    f >> n;
    for (int i = 1; i <= n; i++) f >> v[i].first >> v[i].second;
}

bool conditie (pair <int, int> a, pair <int, int> b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int cauta (int dr) {
    int st = 1, mid, rez = 0;
    int crt = dr + 1;
    while (st <= dr) {
        mid = (st + dr) / 2;
        if (v[mid].second > v[crt].first) dr = mid - 1;
        else {
            rez = max(rez, sol[mid]);
            st = mid + 1;
        }
    }
    return rez;
}

void rezolva() {
    sol[1] = v[1].second - v[1].first;
    int crt;
    for (int i = 2; i <= n; i++) {
        crt = cauta(i - 1);
        sol[i] = v[i].second - v[i].first;
        sol[i] = max(sol[i - 1], sol[i] + crt);
    }

    g << sol[n] << '\n';
}

int main () {
    citeste();
    sort(v + 1, v + n + 1, conditie);
    rezolva();
    return 0;
}