Submission #48170121

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/segtree>

namespace {
    using ModInt [[maybe_unused]] = atcoder::modint998244353;
    using Num [[maybe_unused]] = long long int;
    using Vec [[maybe_unused]] = std::vector<Num>;
    using Set [[maybe_unused]] = std::set<Num>;
    using Mset [[maybe_unused]] = std::multiset<Num>;
    using Edges [[maybe_unused]] = std::vector<std::vector<Num>>;

    template<typename T>
    using Q [[maybe_unused]] = std::queue<T>;

    constexpr Num MinCost = -1000000000000000LL;

    Num apply(Num a, Num b) {
        return std::max(a, b);
    }

    Num unit(void) {
        return MinCost;
    }
}

void solve(std::istream& is, std::ostream& os) {
    Num n, m, l;
    is >> n >> m >> l;

    std::vector<Num> aset(n);
    for(auto&& a : aset) {
        is >> a;
    }

    std::vector<Num> bset(m);
    atcoder::segtree<Num, apply, unit> tree(m);
    for(Num i{0}; i<m; ++i) {
        Num b;
        is >> b;
        bset.at(i) = b;
        tree.set(i, b);
    }

    Edges edges(n);
    for(Num i{0}; i<l; ++i) {
        Num c, d;
        is >> c >> d;
        --c;
        --d;
        edges[c].push_back(d);
    }

    Num answer {0};
    for(Num i{0}; i<n; ++i) {
        for(const auto& b : edges[i]) {
            tree.set(b, MinCost);
        }

        const auto s = aset.at(i) + tree.prod(0, m);
        answer = std::max(answer, s);

        for(const auto& b : edges[i]) {
            tree.set(b, bset.at(b));
        }
    }

    os << answer << "\n";
}

int main(void) {
    solve(std::cin, std::cout);
    return 0;
}

Submission Info

Judge Result