Cod sursa(job #1430618)

Utilizator alexandru.jercaianuJercaianu Alexandru alexandru.jercaianu Data 8 mai 2015 17:46:20
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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[100000];

int bs(vector<pair<int, int>>& v, int a) {
    int l = 0, r = N - 1;
    int aux, currentMax = 0;
    while (l <= r) {
        int m = (l + r)/2;
        if (v[m].second <= a && v[m].second > currentMax) {
            currentMax = v[m].second;
            aux = m;
        }
        
        if (a < v[m].second) {
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return aux;
}

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;
            });


    //cout << v[bs(v, 6)].second << endl;

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

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