Submission #50372560

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    PairVector edges(M);

    for (auto &[u, v] : edges)
        std::cin >> u >> v;

    ValueVector W(N + 1, 0), A(N + 1, 0);

    for (valueType i = 1; i <= N; ++i)
        std::cin >> W[i];

    for (valueType i = 1; i <= N; ++i)
        std::cin >> A[i];

    ValueMatrix G(N + 1);

    ValueVector InDegree(N + 1, 0);

    for (auto const &[u, v] : edges) {
        if (W[u] > W[v]) {
            G[u].push_back(v);

            ++InDegree[v];
        } else if (W[v] > W[u]) {
            G[v].push_back(u);

            ++InDegree[u];
        }
    }

    std::queue<valueType> Queue;
    ValueVector Topo;
    Topo.reserve(N);

    for (valueType i = 1; i <= N; ++i) {
        if (InDegree[i] == 0)
            Queue.push(i);
    }

    while (!Queue.empty()) {
        valueType const x = Queue.front();

        Queue.pop();
        Topo.push_back(x);

        for (auto const &to : G[x])
            if (--InDegree[to] == 0)
                Queue.push(to);
    }

    std::reverse(Topo.begin(), Topo.end());

    ValueVector F(N + 1, 1);
    ValueMatrix S(N + 1);

    for (auto const &x : Topo) {
        ValueVector Max(W[x], 0), Path(W[x], -1);

        for (auto const &to : G[x]) {
            for (valueType i = W[x] - 1; i >= W[to]; --i) {
                if (Max[i] < Max[i - W[to]] + F[to]) {
                    Max[i] = Max[i - W[to]] + F[to];

                    Path[i] = to;
                }
            }
        }

        for (valueType i = 0; i < W[x]; ++i)
            F[x] = std::max(F[x], Max[i] + 1);
    }


    std::reverse(Topo.begin(), Topo.end());

    valueType ans = 0;

    for (valueType i = 1; i <= N; ++i)
        ans += A[i] * F[i];

    std::cout << ans << std::endl;

    return 0;
}

Submission Info

Judge Result