Cod sursa(job #2909762)

Utilizator SeracovanuEdwardSeracovanu Edward SeracovanuEdward Data 15 iunie 2022 15:12:13
Problema Heavy metal Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

int n;
pair <int,int> A[100005];
int dp[100005];

inline bool cmp(pair<int,int> a,pair<int,int> b){
if(a.second > b.second)
    return false;
if(a.second < b.second)
    return true;
return a.first < b.first;
}

int main()
{
    freopen("heavymetal.in","r",stdin);
    freopen("heavymetal.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for(int i = 1;i <= n; ++i)
        cin >> A[i].first >> A[i].second;
    sort(A + 1 ,A + 1 + n ,cmp);
    int j = 1;
    for(int i = 1;i <= A[n].second; ++i){
        dp[i] = dp[i-1];
        while(i == A[j].second){
            if(dp[A[j].first] + A[j].second - A[j].first > dp[i])
                dp[i] = dp[A[j].first] + A[j].second - A[j].first;
        ++j;
        }
    }
    cout << dp[A[n].second];
}