Cod sursa(job #3347324)

Utilizator alexkAlexandru Kelemen alexk Data 16 martie 2026 11:33:35
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int nmax=1e5;
int n, dp[nmax+5];
struct concert
{
    int a, b;
};
vector<concert>v(nmax+5);
bool cmp(concert x, concert y)
{
    return x.b<y.b;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>v[i].a>>v[i].b;
    sort(v.begin()+1, v.begin()+n+1, cmp);
    for(int i=1;i<=n;i++)
    {
        concert target;
        target.b=v[i].a;
        auto up=upper_bound(v.begin()+1, v.begin()+i, target, cmp);
        int idx=up-v.begin()-1;
        dp[i]=max(dp[i-1], (v[i].b-v[i].a)+dp[idx]);
    }
    cout<<dp[n];
    return 0;
}