Cod sursa(job #3281563)

Utilizator lucaclgluca clg lucaclg Data 2 martie 2025 12:53:15
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, i, j, dp[100001];
vector <pair<int, int>> v;
int cb(int st, int dr, int x)
{
    int poz = -1;
    while(st <= dr)
    {
        int mij = (st + dr)  / 2;
        if(v[mij].second <= x)
        {
            poz = mij;
            st = mij + 1;
        }
        else if(v[mij].second > x)
            dr = mij - 1;
    }
    return poz;
}
bool cmp (pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}
int main()
{
    fin >> n;
    for(i = 0; i < n; i++)
    {
        int x, y;
        fin >> x >> y;
        v.push_back({x, y});
    }
    sort(v.begin(), v.end(), cmp);
    dp[0] = v[0].second - v[0].first;
    for(i = 1; i < n; i++){
        j = cb(0, i - 1, v[i].first);
        if(j != -1)
            dp[i] = max(dp[i - 1], (v[i].second - v[i].first) + dp[j]);
        else
            dp[i] = dp[i - 1];
    }
    fout << dp[n - 1];
    return 0;
}