Cod sursa(job #3295332)

Utilizator Barbu_MateiBarbu Matei Barbu_Matei Data 4 mai 2025 14:44:46
Problema Heavy metal Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

int n;
pair<int, int> v[100001];
pair<int, int> dp[100001];

int main() {
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    dp[1] = {v[1].second, v[1].second - v[1].first};
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (v[i].first >= v[j].second) {
                dp[i].second = max(dp[i].second, dp[j].second);
            }
        }
        dp[i] = {v[i].second, dp[i].second + v[i].second - v[i].first};
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, dp[i].second);
    }
    cout << ans;
}