A841 炼金术 全站最快题解

#include <iostream>
#include <vector>
#include <numeric>

bool is_producible(long long num_to_make, int n,
                   const std::vector<long long>& initial_metals,
                   const std::vector<std::vector<int>>& recipes,
                   long long safe_cap) {
    std::vector<long long> needed(n + 1, 0);
    needed[n] = num_to_make;

    for (int i = n; i >= 1; --i) {
        if (needed[i] == 0) {
            continue;
        }

        if (needed[i] > initial_metals[i]) {
            long long deficit = needed[i] - initial_metals[i];
            
            if (recipes[i].empty()) {
                return false;
            }
            
            for (int ingredient : recipes[i]) {
                needed[ingredient] += deficit;
                if (needed[ingredient] > safe_cap) {
                    needed[ingredient] = safe_cap;
                }
            }
        }
    }
    
    return true;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<long long> initial_metals(n + 1);
    long long total_initial_metals = 0;
    for (int i = 1; i <= n; ++i) {
        std::cin >> initial_metals[i];
        total_initial_metals += initial_metals[i];
    }

    int k;
    std::cin >> k;

    std::vector<std::vector<int>> recipes(n + 1);
    for (int i = 0; i < k; ++i) {
        int l, m;
        std::cin >> l >> m;
        recipes[l].resize(m);
        for (int j = 0; j < m; ++j) {
            std::cin >> recipes[l][j];
        }
    }

    long long low = 0;
    long long high = total_initial_metals;
    long long max_producible = 0;
    long long safe_cap = total_initial_metals + 1;

    while (low <= high) {
        long long mid = low + (high - low) / 2;
        
        if (is_producible(mid, n, initial_metals, recipes, safe_cap)) {
            max_producible = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    std::cout << max_producible << '\n';

    return 0;
}