Cod sursa(job #3313481)

Utilizator MegaCoderMinoiu Teodor Mihai MegaCoder Data 4 octombrie 2025 18:34:36
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define ll long long
std::ifstream fin("heavymetal.in");
std::ofstream fout("heavymetal.out");
std::vector<std::pair<int, int>>v;
int n;

void read()
{
    fin>>n;
    v.emplace_back(0, 0);
    for(int i=1; i<=n; ++i)
    {
        int l, r;
        fin>>l>>r;
        v.emplace_back(l, r);
    }
    std::sort(v.begin(), v.end(), [](std::pair<int, int>a, std::pair<int, int>b){
        return a.second<b.second;
    });
}
inline int find_left(int idx)
{
    int lg;
    for(lg=1; lg<n; lg<<=1);
    int pos=0;
    for(int d=lg; d; d>>=1)
    {
        if(pos+d<=n && v[pos+d].second<=v[idx].first)
            pos+=d;
    }
    return pos;
}
void solve()
{
    std::vector<ll>dp(n+5);//solutia care include intervalul i
    std::vector<ll>best(n+5);//solutia cea mai buna pana la i
    dp[0]=best[0]=0;
    for(int i=1; i<=n; ++i)
    {
        int idx=find_left(i);
        dp[i]=best[idx]+v[i].second-v[i].first;
        best[i]=std::max(dp[i], best[i-1]);
    }
    fout<<best[n];
}
int main()
{
    read();
    solve();
    return 0;
}