Cod sursa(job #2515279)

Utilizator dragos99Homner Dragos dragos99 Data 28 decembrie 2019 11:53:31
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include<bits/stdc++.h>
using namespace std;
    ifstream f("heavymetal.in");
    ofstream g("heavymetal.out");

const int NMAX = 100001;

int n;
int dp[NMAX];
vector<pair<int, int> > intervals;

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return (a.second < b.second);
}

int binSearch(int left, int right, int val)
{
    int mid = 0, sol = -1;
    while(left <= right){
        mid = left + (right - left) / 2;
        if(intervals[mid].second <= val){
            left = mid + 1;
            sol = mid;
        }
        else{
            right = mid - 1;
        }
    }
    if(sol >= 0){
        return dp[sol];
    }
    return 0;
}

int main()
{
    f>>n;
    intervals.resize(n);
    for(auto &x: intervals){
        f>>x.first>>x.second;
    }

    sort(intervals.begin(), intervals.end(), cmp);

    dp[0] = intervals[0].second - intervals[0].first;
    for(int i = 1 ; i < n ; i++){
        dp[i] = max(dp[i - 1], intervals[i].second - intervals[i].first + binSearch(0, i, intervals[i].first));
    }

    g<<dp[n - 1];

    return 0;
}