Cod sursa(job #2356605)

Utilizator vladsftVlad Safta vladsft Data 26 februarie 2019 20:10:22
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

const int N = 100001;
long long dp[N];
int a[N], b[N], d[100001];
int n;
struct numar{
    int stt, drr;
};
numar v[100001];
int cmp(numar a, numar b){
    if (a.drr == b.drr)
        return a.stt < b.stt;
    return a.drr < b.drr;
}

int caut(int k, int dr)
{
    int st = 1, ans = 0, mij;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        if (v[mij].drr <= k)
        {
            ans = mij;
            st = mij + 1;
        }
        else dr = mij - 1;
    }
    return ans;
}
int main()
{
    int n, ans;
    f >> n;
    for (int i = 1; i <= n; i++)
    {
        f >> v[i].stt >> v[i].drr;
    }
    sort (v + 1, v + n + 1, cmp);
    dp[1] = v[1].drr - v[1].stt;
    for (int i = 2; i <= n; i++)
    {
        ans = caut(v[i].stt, i - 1);
        dp[i] = max(dp[i - 1], dp[ans] + v[i].drr - v[i].stt);
    }
    g << dp[n];
    return 0;
}