Cod sursa(job #2988221)

Utilizator brianna_enacheEnache Brianna brianna_enache Data 3 martie 2023 20:15:50
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct Interval
{
    int st, dr;
}a[100005];

int Cmp(Interval A, Interval B)
{
    return A.dr < B.dr;
}
int n, dp[100005];

///caut binar cea mai din dreapta pozitie cu capatul drept
///mai mic sau egal decat a[i].st
int CautBin(int x)
{
    int s, d, mij, poz;
    s = 1; d = n; poz = 0;
    while(s <= d)
    {
        mij = (s + d)/2;
        if(a[mij].dr <= x)
        {
            poz = mij;
            s = mij + 1;
        }
        else d = mij - 1;
    }
    return poz;
}
int main()
{
    int i;
    in >> n;
    for(i = 1; i <= n; i++)
    {
        in >> a[i].st >> a[i].dr;
    }
    sort(a + 1,  a + 1 + n, Cmp);
    for(i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1];
        int k = CautBin(a[i].st);
        dp[i] = max(dp[i], dp[k] + a[i].dr - a[i].st);
    }
    out << dp[n] << " ";
    return 0;
}