Cod sursa(job #1430628)

Utilizator alexandru.jercaianuJercaianu Alexandru alexandru.jercaianu Data 8 mai 2015 18:07:20
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int N;
int a[100002], b[100002], d[100001];

int bs(vector<pair<int, int>>& v, int a, int r) {
    int l = 0;
    int aux = -1, currentMax = 0;

    r--;
    while (l <= r) {
        int m = (l + r)/2;

        if (v[m].second <= a && v[m].second >= currentMax) {
            if (currentMax == v[m].second) {
                aux = max(aux, m);
            } else {
                aux = m;
            }
            currentMax = v[m].second;
        }
        
        if (a < v[m].second) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }

    return aux + 1;
}

int main() 
{
    fin >> N;
    vector<pair<int, int>> v(N);
    int m = 0;
    for (int i = 0; i < N; i++) {
        int x, y;
        fin >> x >> y;
        v[i] = make_pair(x, y);
    }
    
    sort(v.begin(), v.end(), 
            [](const pair<int,int>& p1, const pair<int, int>& p2) {
                return p1.second < p2.second;
            });

    d[0] = 0;
    d[1] = v[0].second - v[0].first;
    for (int i = 2; i <= N; i++) {
        d[i] = max(d[i - 1], d[bs(v, v[i - 1].first, i - 1)] + v[i - 1].second - v[i - 1].first);
    }

    fout << d[N] << endl;
}