Cod sursa(job #2287488)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 21 noiembrie 2018 22:36:46
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 100000;

int DP[NMAX + 5], N;

struct interval{int start, finish;} V[NMAX + 5];

inline bool compare(interval a, interval b) {
    return a.finish < b.finish;
}

int caut(int st, int dr, int val)
{
    int ans = 0;

    while(st <= dr) {
        int mid = (st + dr) >> 1;

        if(V[mid].finish <= val) {
            ans = DP[mid];
            st = mid + 1;
        } else {
            dr = mid - 1;
        }
    }
    return ans;
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> V[i].start >> V[i].finish;

    sort(V + 1, V + N + 1, compare);

    for(int i = 1; i <= N; i++)
        DP[i] = max(DP[i - 1], caut(1, i - 1, V[i].start) + V[i].finish - V[i].start);

    fout << DP[N] << '\n';

    return 0;
}