結果
問題 |
No.3201 Corporate Synergy
|
ユーザー |
|
提出日時 | 2025-07-12 18:40:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 44,514 bytes |
コンパイル時間 | 1,940 ms |
コンパイル使用メモリ | 158,176 KB |
実行使用メモリ | 6,272 KB |
最終ジャッジ日時 | 2025-07-12 18:40:53 |
合計ジャッジ時間 | 2,924 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <cassert> #include <map> #include <string> #include <bitset> #include <array> #include <unordered_set> #include <iomanip> #include <utility> #include <vector> #include <istream> #include <stack> #include <ostream> #include <list> #include <deque> #include <unordered_map> #include <iostream> #include <set> #include <algorithm> #include <functional> #include <queue> #include <limits> #include <fstream> #include <type_traits> #include <numeric> #include <optional> #include <iterator> #ifndef KK2_TEMPLATE_PROCON_HPP #define KK2_TEMPLATE_PROCON_HPP 1 #ifndef KK2_TEMPLATE_CONSTANT_HPP #define KK2_TEMPLATE_CONSTANT_HPP 1 #ifndef KK2_TEMPLATE_TYPE_ALIAS_HPP #define KK2_TEMPLATE_TYPE_ALIAS_HPP 1 using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; using i128 = __int128_t; using u128 = __uint128_t; using pi = std::pair<int, int>; using pl = std::pair<i64, i64>; using pil = std::pair<int, i64>; using pli = std::pair<i64, int>; template <class T> using vc = std::vector<T>; template <class T> using vvc = std::vector<vc<T>>; template <class T> using vvvc = std::vector<vvc<T>>; template <class T> using vvvvc = std::vector<vvvc<T>>; template <class T> using pq = std::priority_queue<T>; template <class T> using pqi = std::priority_queue<T, std::vector<T>, std::greater<T>>; #endif // KK2_TEMPLATE_TYPE_ALIAS_HPP template <class T> constexpr T infty = 0; template <> constexpr int infty<int> = (1 << 30) - 123; template <> constexpr i64 infty<i64> = (1ll << 62) - (1ll << 31); template <> constexpr i128 infty<i128> = (i128(1) << 126) - (i128(1) << 63); template <> constexpr u32 infty<u32> = infty<int>; template <> constexpr u64 infty<u64> = infty<i64>; template <> constexpr u128 infty<u128> = infty<i128>; template <> constexpr double infty<double> = infty<i64>; template <> constexpr long double infty<long double> = infty<i64>; constexpr int mod = 998244353; constexpr int modu = 1e9 + 7; constexpr long double PI = 3.14159265358979323846; #endif // KK2_TEMPLATE_CONSTANT_HPP #ifndef KK2_TEMPLATE_FUNCTION_UTIL_HPP #define KK2_TEMPLATE_FUNCTION_UTIL_HPP 1 #ifndef KK2_MATH_MONOID_MAX_HPP #define KK2_MATH_MONOID_MAX_HPP 1 #ifndef KK2_TYPE_TRAITS_IO_HPP #define KK2_TYPE_TRAITS_IO_HPP 1 namespace kk2 { namespace type_traits { struct istream_tag {}; struct ostream_tag {}; } // namespace type_traits template <typename T> using is_standard_istream = typename std::conditional<std::is_same<T, std::istream>::value || std::is_same<T, std::ifstream>::value, std::true_type, std::false_type>::type; template <typename T> using is_standard_ostream = typename std::conditional<std::is_same<T, std::ostream>::value || std::is_same<T, std::ofstream>::value, std::true_type, std::false_type>::type; template <typename T> using is_user_defined_istream = std::is_base_of<type_traits::istream_tag, T>; template <typename T> using is_user_defined_ostream = std::is_base_of<type_traits::ostream_tag, T>; template <typename T> using is_istream = typename std::conditional<is_standard_istream<T>::value || is_user_defined_istream<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_ostream = typename std::conditional<is_standard_ostream<T>::value || is_user_defined_ostream<T>::value, std::true_type, std::false_type>::type; template <typename T> using is_istream_t = std::enable_if_t<is_istream<T>::value>; template <typename T> using is_ostream_t = std::enable_if_t<is_ostream<T>::value>; } // namespace kk2 #endif // KK2_TYPE_TRAITS_IO_HPP namespace kk2 { namespace monoid { template <class S, class Compare = std::less<S>> struct Max { static constexpr bool commutative = true; using M = Max; S a; bool is_unit; Max() : a(S()), is_unit(true) {} Max(S a_) : a(a_), is_unit(false) {} operator S() const { return a; } inline static M op(M l, M r) { if (l.is_unit or r.is_unit) return l.is_unit ? r : l; return Compare{}(l.a, r.a) ? r : l; } inline static M unit() { return M(); } bool operator==(const M &rhs) const { return is_unit == rhs.is_unit and (is_unit or a == rhs.a); } bool operator!=(const M &rhs) const { return is_unit != rhs.is_unit or (!is_unit and a != rhs.a); } template <class OStream, is_ostream_t<OStream> * = nullptr> friend OStream &operator<<(OStream &os, const M &x) { if (x.is_unit) os << "-inf"; else os << x.a; return os; } template <class IStream, is_istream_t<IStream> * = nullptr> friend IStream &operator>>(IStream &is, M &x) { is >> x.a; x.is_unit = false; return is; } }; } // namespace monoid } // namespace kk2 #endif // MATH_MONOID_MAX_HPP #ifndef KK2_MATH_MONOID_MIN_HPP #define KK2_MATH_MONOID_MIN_HPP 1 namespace kk2 { namespace monoid { template <class S, class Compare = std::less<S>> struct Min { static constexpr bool commutative = true; using M = Min; S a; bool is_unit; Min() : a(S()), is_unit(true) {} Min(S a_) : a(a_), is_unit(false) {} operator S() const { return a; } inline static M op(M l, M r) { if (l.is_unit or r.is_unit) return l.is_unit ? r : l; return Compare{}(l.a, r.a) ? l : r; } inline static M unit() { return M(); } bool operator==(const M &rhs) const { return is_unit == rhs.is_unit and (is_unit or a == rhs.a); } bool operator!=(const M &rhs) const { return is_unit != rhs.is_unit or (!is_unit and a != rhs.a); } template <class OStream, is_ostream_t<OStream> * = nullptr> friend OStream &operator<<(OStream &os, const M &x) { if (x.is_unit) os << "inf"; else os << x.a; return os; } template <class IStream, is_istream_t<IStream> * = nullptr> friend IStream &operator>>(IStream &is, M &x) { is >> x.a; x.is_unit = false; return is; } }; } // namespace monoid } // namespace kk2 #endif // KK2_MATH_MONOID_MIN_HPP #ifndef KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP #define KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP 1 namespace kk2 { template <typename T> struct is_vector : std::false_type {}; template <typename T, typename Alloc> struct is_vector<std::vector<T, Alloc>> : std::true_type {}; // コンテナかどうかを判定するtraits template <typename T> struct is_container : std::false_type {}; // 基本的なコンテナ型の特殊化 template <typename T, typename Alloc> struct is_container<std::vector<T, Alloc>> : std::true_type { }; template <typename CharT, typename Traits, typename Alloc> struct is_container<std::basic_string<CharT, Traits, Alloc>> : std::true_type {}; template <typename T, std::size_t N> struct is_container<std::array<T, N>> : std::true_type {}; template <typename T, typename Alloc> struct is_container<std::deque<T, Alloc>> : std::true_type {}; template <typename T, typename Alloc> struct is_container<std::list<T, Alloc>> : std::true_type {}; // SFINAEでコンテナを判定するためのヘルパー template <typename T> using is_container_t = typename std::enable_if_t<is_container<T>::value, std::nullptr_t>; } // namespace kk2 #endif // KK2_TYPE_TRAITS_CONTAINER_TRAITS_HPP namespace kk2 { template <class T, class... Sizes> auto make_vector(int first, Sizes... sizes) { if constexpr (sizeof...(sizes) == 0) { return std::vector<T>(first); } else { return std::vector<decltype(make_vector<T>(sizes...))>(first, make_vector<T>(sizes...)); } } template <class T, class U> void fill_all(std::vector<T> &v, const U &x) { if constexpr (is_vector<T>::value) { for (auto &u : v) fill_all(u, x); } else { std::fill(v.begin(), v.end(), T(x)); } } template <class T, class U> int iota_all(std::vector<T> &v, U x, int offset = 0) { if constexpr (is_vector<T>::value) { for (auto &u : v) offset += iota_all(u, x + offset); } else { for (auto &u : v) u = x++, ++offset; } return offset; } template <class C> int mysize(const C &c) { return size(c); } // T: commutative monoid, F: (U, T) -> U template <class U, class T, class F> U all_monoid_prod(const std::vector<T> &v, U unit, const F &f) { U res = unit; if constexpr (is_vector<T>::value) { for (const auto &x : v) res = f(res, all_monoid_prod(x, unit, f)); } else { for (const auto &x : v) res = f(res, x); } return res; } template <class U, class T> U all_sum(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a + b; }); } template <class U, class T> U all_prod(const std::vector<T> &v, U unit = U(1)) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a * b; }); } template <class U, class T> U all_xor(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a ^ b; }); } template <class U, class T> U all_and(const std::vector<T> &v, U unit = U(-1)) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a & b; }); } template <class U, class T> U all_or(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return a | b; }); } template <class U, class T> U all_min(const std::vector<T> &v) { return all_monoid_prod<monoid::Min<U>, T>(v, monoid::Min<U>::unit(), monoid::Min<U>::op); } template <class U, class T> U all_max(const std::vector<T> &v) { return all_monoid_prod<monoid::Max<U>, T>(v, monoid::Max<U>::unit(), monoid::Max<U>::op); } template <class U, class T> U all_gcd(const std::vector<T> &v, U unit = U()) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::gcd(a, b); }); } template <class U, class T> U all_lcm(const std::vector<T> &v, U unit = U(1)) { return all_monoid_prod<U, T>(v, unit, [](U a, U b) { return std::lcm(a, b); }); } } // namespace kk2 #endif // KK2_TEMPLATE_FUNCTION_UTIL_HPP #ifndef KK2_TEMPLATE_IO_UTIL_HPP #define KK2_TEMPLATE_IO_UTIL_HPP 1 // なんかoj verifyはプロトタイプ宣言が落ちる namespace impl { struct read { template <class IStream, class T> inline static void all_read(IStream &is, T &x) { is >> x; } template <class IStream, class T, class U> inline static void all_read(IStream &is, std::pair<T, U> &p) { all_read(is, p.first); all_read(is, p.second); } template <class IStream, class T> inline static void all_read(IStream &is, std::vector<T> &v) { for (T &x : v) all_read(is, x); } template <class IStream, class T, size_t F> inline static void all_read(IStream &is, std::array<T, F> &a) { for (T &x : a) all_read(is, x); } }; struct write { template <class OStream, class T> inline static void all_write(OStream &os, const T &x) { os << x; } template <class OStream, class T, class U> inline static void all_write(OStream &os, const std::pair<T, U> &p) { all_write(os, p.first); all_write(os, ' '); all_write(os, p.second); } template <class OStream, class T> inline static void all_write(OStream &os, const std::vector<T> &v) { for (int i = 0; i < (int)v.size(); ++i) { if (i) all_write(os, ' '); all_write(os, v[i]); } } template <class OStream, class T, size_t F> inline static void all_write(OStream &os, const std::array<T, F> &a) { for (int i = 0; i < (int)F; ++i) { if (i) all_write(os, ' '); all_write(os, a[i]); } } }; } // namespace impl template <class IStream, class T, class U, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::pair<T, U> &p) { impl::read::all_read(is, p); return is; } template <class IStream, class T, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::vector<T> &v) { impl::read::all_read(is, v); return is; } template <class IStream, class T, size_t F, kk2::is_istream_t<IStream> * = nullptr> IStream &operator>>(IStream &is, std::array<T, F> &a) { impl::read::all_read(is, a); return is; } template <class OStream, class T, class U, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::pair<T, U> &p) { impl::write::all_write(os, p); return os; } template <class OStream, class T, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::vector<T> &v) { impl::write::all_write(os, v); return os; } template <class OStream, class T, size_t F, kk2::is_ostream_t<OStream> * = nullptr> OStream &operator<<(OStream &os, const std::array<T, F> &a) { impl::write::all_write(os, a); return os; } #endif // KK2_TEMPLATE_IO_UTIL_HPP #ifndef KK2_TEMPLATE_MACROS_HPP #define KK2_TEMPLATE_MACROS_HPP 1 #define rep1(a) for (long long _ = 0; _ < (long long)(a); ++_) #define rep2(i, a) for (long long i = 0; i < (long long)(a); ++i) #define rep3(i, a, b) for (long long i = (a); i < (long long)(b); ++i) #define repi2(i, a) for (long long i = (a) - 1; i >= 0; --i) #define repi3(i, a, b) for (long long i = (a) - 1; i >= (long long)(b); --i) #define overload3(a, b, c, d, ...) d #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define repi(...) overload3(__VA_ARGS__, repi3, repi2, rep1)(__VA_ARGS__) #define fi first #define se second #define all(p) begin(p), end(p) #endif // KK2_TEMPLATE_MACROS_HPP struct FastIOSetUp { FastIOSetUp() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } fast_io_set_up; auto &kin = std::cin; auto &kout = std::cout; auto (*kendl)(std::ostream &) = std::endl<char, std::char_traits<char>>; void Yes(bool b = 1) { kout << (b ? "Yes\n" : "No\n"); } void No(bool b = 1) { kout << (b ? "No\n" : "Yes\n"); } void YES(bool b = 1) { kout << (b ? "YES\n" : "NO\n"); } void NO(bool b = 1) { kout << (b ? "NO\n" : "YES\n"); } void yes(bool b = 1) { kout << (b ? "yes\n" : "no\n"); } void no(bool b = 1) { kout << (b ? "no\n" : "yes\n"); } template <class T, class S> inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template <class T, class S> inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } std::istream &operator>>(std::istream &is, u128 &x) { std::string s; is >> s; x = 0; for (char c : s) { assert('0' <= c && c <= '9'); x = x * 10 + c - '0'; } return is; } std::istream &operator>>(std::istream &is, i128 &x) { std::string s; is >> s; bool neg = s[0] == '-'; x = 0; for (int i = neg; i < (int)s.size(); i++) { assert('0' <= s[i] && s[i] <= '9'); x = x * 10 + s[i] - '0'; } if (neg) x = -x; return is; } std::ostream &operator<<(std::ostream &os, u128 x) { if (x == 0) return os << '0'; std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } std::ostream &operator<<(std::ostream &os, i128 x) { if (x == 0) return os << '0'; if (x < 0) { os << '-'; x = -x; } std::string s; while (x) { s.push_back('0' + x % 10); x /= 10; } std::reverse(s.begin(), s.end()); return os << s; } #endif // KK2_TEMPLATE_PROCON_HPP #ifndef KK2_TEMPLATE_DEBUG_HPP #define KK2_TEMPLATE_DEBUG_HPP 1 #ifndef KK2_TYPE_TRAITS_MEMBER_HPP #define KK2_TYPE_TRAITS_MEMBER_HPP 1 namespace kk2 { #define HAS_MEMBER_FUNC(member) \ template <typename T, typename... Ts> struct has_member_func_##member##_impl { \ template <typename U> \ static std::true_type check(decltype(std::declval<U>().member(std::declval<Ts>()...)) *); \ template <typename U> static std::false_type check(...); \ using type = decltype(check<T>(nullptr)); \ }; \ template <typename T, typename... Ts> struct has_member_func_##member \ : has_member_func_##member##_impl<T, Ts...>::type {}; \ template <typename T, typename... Ts> using has_member_func_##member##_t = \ std::enable_if_t<has_member_func_##member<T, Ts...>::value>; \ template <typename T, typename... Ts> using not_has_member_func_##member##_t = \ std::enable_if_t<!has_member_func_##member<T, Ts...>::value>; #define HAS_MEMBER_VAR(member) \ template <typename T> struct has_member_var_##member##_impl { \ template <typename U> static std::true_type check(decltype(std::declval<U>().member) *); \ template <typename U> static std::false_type check(...); \ using type = decltype(check<T>(nullptr)); \ }; \ template <typename T> struct has_member_var_##member \ : has_member_var_##member##_impl<T>::type {}; \ template <typename T> using has_member_var_##member##_t = \ std::enable_if_t<has_member_var_##member<T>::value>; \ template <typename T> using not_has_member_var_##member##_t = \ std::enable_if_t<!has_member_var_##member<T>::value>; HAS_MEMBER_FUNC(debug_output) HAS_MEMBER_FUNC(val) #undef HAS_MEMBER_FUNC #undef HAS_MEMBER_VAR } // namespace kk2 #endif // KK2_TYPE_TRAITS_MEMBER_HPP namespace kk2 { namespace debug { #ifdef KK2 template <class OStream, is_ostream_t<OStream> *> void output(OStream &os); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const T &t); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::vector<T> &v); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::vector<std::vector<T>> &d); template <class OStream, class T, size_t F, is_ostream_t<OStream> *> void output(OStream &os, const std::array<T, F> &a); template <class OStream, class T, class U, is_ostream_t<OStream> *> void output(OStream &os, const std::pair<T, U> &p); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::queue<T> &q); template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> *> void output(OStream &os, const std::priority_queue<T, Container, Compare> &q); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::deque<T> &d); template <class OStream, class T, is_ostream_t<OStream> *> void output(OStream &os, const std::stack<T> &s); template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::set<Key, Compare, Allocator> &s); template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s); template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s); template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s); template <class OStream, class Key, class T, class Compare, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m); template <class OStream, class Key, class T, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> *> void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m); template <class OStream, is_ostream_t<OStream> * = nullptr> void output(OStream &) {} template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const T &t) { if constexpr (has_member_func_debug_output<T, OStream &>::value) { t.debug_output(os); } else { os << t; } } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::vector<T> &v) { os << "["; for (int i = 0; i < (int)v.size(); i++) { output(os, v[i]); if (i + 1 != (int)v.size()) os << ", "; } os << "]"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::vector<std::vector<T>> &d) { os << "[\n"; for (int i = 0; i < (int)d.size(); i++) { output(os, d[i]); output(os, "\n"); } os << "]"; } template <class OStream, class T, size_t F, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::array<T, F> &a) { os << "["; for (int i = 0; i < (int)F; i++) { output(os, a[i]); if (i + 1 != (int)F) os << ", "; } os << "]"; } template <class OStream, class T, class U, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::pair<T, U> &p) { os << "("; output(os, p.first); os << ", "; output(os, p.second); os << ")"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::queue<T> &q) { os << "["; std::queue<T> tmp = q; while (!tmp.empty()) { output(os, tmp.front()); tmp.pop(); if (!tmp.empty()) os << ", "; } os << "]"; } template <class OStream, class T, class Container, class Compare, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::priority_queue<T, Container, Compare> &q) { os << "["; std::priority_queue<T, Container, Compare> tmp = q; while (!tmp.empty()) { output(os, tmp.top()); tmp.pop(); if (!tmp.empty()) os << ", "; } os << "]"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::deque<T> &d) { os << "["; std::deque<T> tmp = d; while (!tmp.empty()) { output(os, tmp.front()); tmp.pop_front(); if (!tmp.empty()) os << ", "; } os << "]"; } template <class OStream, class T, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::stack<T> &s) { os << "["; std::stack<T> tmp = s; std::vector<T> v; while (!tmp.empty()) { v.push_back(tmp.top()); tmp.pop(); } for (int i = (int)v.size() - 1; i >= 0; i--) { output(os, v[i]); if (i != 0) os << ", "; } os << "]"; } template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::set<Key, Compare, Allocator> &s) { os << "{"; std::set<Key, Compare, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class Compare, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::multiset<Key, Compare, Allocator> &s) { os << "{"; std::multiset<Key, Compare, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::unordered_set<Key, Hash, KeyEqual, Allocator> &s) { os << "{"; std::unordered_set<Key, Hash, KeyEqual, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::unordered_multiset<Key, Hash, KeyEqual, Allocator> &s) { os << "{"; std::unordered_multiset<Key, Hash, KeyEqual, Allocator> tmp = s; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, *it); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class T, class Compare, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::map<Key, T, Compare, Allocator> &m) { os << "{"; std::map<Key, T, Compare, Allocator> tmp = m; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, it->first); os << ": "; output(os, it->second); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class Key, class T, class Hash, class KeyEqual, class Allocator, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const std::unordered_map<Key, T, Hash, KeyEqual, Allocator> &m) { os << "{"; std::unordered_map<Key, T, Hash, KeyEqual, Allocator> tmp = m; for (auto it = tmp.begin(); it != tmp.end(); ++it) { output(os, it->first); os << ": "; output(os, it->second); if (std::next(it) != tmp.end()) os << ", "; } os << "}"; } template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr> void output(OStream &os, const T &t, const Args &...args) { output(os, t); os << ' '; output(os, args...); } template <class OStream, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os) { os << '\n'; os.flush(); } template <class OStream, class T, class... Args, is_ostream_t<OStream> * = nullptr> void outputln(OStream &os, const T &t, const Args &...args) { output(os, t, args...); os << '\n'; os.flush(); } std::vector<std::string> sep(const char *s) { std::vector<std::string> res; std::string now; int dep = 0; while (true) { if (*s == '\0') { res.emplace_back(now); break; } if (*s == '(' or *s == '[' or *s == '{') dep++; if (*s == ')' or *s == ']' or *s == '}') dep--; if (dep == 0 and *s == ',') { res.emplace_back(now); now.clear(); } else if (!isspace(*s)) { now += *s; } s++; } return res; } void show_vars(const std::vector<std::string> &, int) {} template <class T, class... Args> void show_vars(const std::vector<std::string> &name, int pos, const T &t, const Args &...args) { // assert(pos < (int)name.size()); output(std::cerr, name[pos++] + ":", t); if (sizeof...(args) > 0) output(std::cerr, ", "); show_vars(name, pos, args...); } #define kdebug(...) \ std::cerr << "line:" << __LINE__ << ' '; \ kk2::debug::show_vars(kk2::debug::sep(#__VA_ARGS__), 0, __VA_ARGS__); \ std::cerr << std::endl; #define kput(s) \ std::cerr << "line:" << __LINE__ << ' '; \ kk2::debug::outputln(std::cerr, s); #else template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr> void output(OStream &, const Args &...) {} template <class OStream, class... Args, is_ostream_t<OStream> * = nullptr> void outputln(OStream &, const Args &...) {} template <class... Args> void fix_warn(const Args &...) {} #define kdebug(...) kk2::debug::fix_warn(__VA_ARGS__); #define kput(s) kk2::debug::fix_warn(s) #endif // KK2 } // namespace debug } // namespace kk2 #endif // KK2_TEMPLATE_DEBUG_HPP #ifndef KK2_GRAPH_MAXFLOW_HPP #define KK2_GRAPH_MAXFLOW_HPP 1 namespace kk2 { template <class WG> struct MaxFlow { static_assert(WG::directed, "MaxFlow requires directed graph"); static_assert(WG::weighted, "MaxFlow requires weighted graph"); using Cap = typename WG::value_type; WG g; int n, m; std::vector<int> revi; MaxFlow(const WG &g_) : n(g_.num_vertices()), m(g_.num_edges()) { if constexpr (WG::static_graph) { g = WG(n); for (auto &&e : g_.edges) g.add_edge(e.from, e.to, e.cost); for (auto &&e : g_.edges) g.add_edge(e.to, e.from, 0); g.build(); } else { g = g_; for (auto &&e : g_.edges) g.add_edge(e.to, e.from, 0); } revi.resize(2 * m); for (int i = 0; i < n; ++i) { for (int j = 0; j < (int)g[i].size(); ++j) revi[g[i][j].id >= m ? g[i][j].id - m : g[i][j].id + m] = j; } } template <class Edges_> MaxFlow(int n_, const Edges_ &edges) : n(n_), m(edges.size()) { g = WG(n); for (auto &&e : edges) g.add_edge(e.from, e.to, e.cost); for (auto &&e : edges) g.add_edge(e.to, e.from, 0); if constexpr (WG::static_graph) g.build(); revi.resize(2 * m); for (int i = 0; i < n; ++i) { for (int j = 0; j < (int)g[i].size(); ++j) revi[g[i][j].id >= m ? g[i][j].id - m : g[i][j].id + m] = j; } } Cap flow(int s, int t) { return flow(s, t, std::numeric_limits<Cap>::max()); } Cap flow(int s, int t, Cap flow_limit) { assert(0 <= s && s < n); assert(0 <= t && t < n); assert(s != t); std::vector<int> level(n), iter(n); std::queue<int> que; auto bfs = [&]() { std::fill(std::begin(level), std::end(level), -1); level[s] = 0; que = std::queue<int>(); que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (auto &e : g[v]) { if (e.cost == 0 || level[e.to] >= 0) continue; level[e.to] = level[v] + 1; if (e.to == t) return; que.push(e.to); } } }; auto dfs = [&](auto self, int v, Cap up) { if (v == s) return up; Cap res = 0; for (int &i = iter[v]; i < (int)g[v].size(); i++) { auto &e = g[v][i]; if (level[v] <= level[e.to] || g[e.to][revi[e.id]].cost == 0) continue; Cap d = self(self, e.to, std::min(up - res, g[e.to][revi[e.id]].cost)); if (d <= 0) continue; g[v][i].cost += d; g[e.to][revi[e.id]].cost -= d; res += d; if (res == up) break; } return res; }; Cap flow = 0; while (flow < flow_limit) { bfs(); if (level[t] == -1) break; std::fill(std::begin(iter), std::end(iter), 0); while (flow < flow_limit) { Cap f = dfs(dfs, t, flow_limit - flow); if (!f) break; flow += f; } } return flow; } std::vector<bool> min_cut(int s) { std::vector<bool> visited(n); std::queue<int> que; que.push(s); while (!que.empty()) { int p = que.front(); que.pop(); visited[p] = true; for (auto &e : g[p]) { if (e.cost && !visited[e.to]) { visited[e.to] = true; que.push(e.to); } } } return visited; } struct edge { int from, to; Cap cap, flow; }; edge get_edge(int i) { auto e = g.edges[i]; return edge{e.from, e.to, e.cost + g[e.to][revi[i]].cost, g[e.to][revi[i]].cost}; } std::vector<edge> get_edges() { std::vector<edge> result(m); for (int i = 0; i < m; i++) { result[i] = get_edge(i); } return result; } }; } // namespace kk2 #endif // KK2_GRAPH_MAXFLOW_HPP #ifndef KK2_GRAPH_GRAPH_HPP #define KK2_GRAPH_GRAPH_HPP 1 #ifndef KK2_GRAPH_EDGE_HPP #define KK2_GRAPH_EDGE_HPP 1 namespace kk2 { namespace graph { struct empty {}; template <class T> struct _Edge { int from, to, id; T cost; _Edge(int to_, T cost_, int from_ = -1, int id_ = -1) : from(from_), to(to_), id(id_), cost(cost_) {} _Edge() : from(-1), to(-1), id(-1) {} operator int() const { return to; } inline _Edge rev() const { return _Edge(from, cost, to, id); } template <class OStream, is_ostream_t<OStream> * = nullptr> void debug_output(OStream &os) const { os << '(' << id << ", " << from << "->" << to; if constexpr (!std::is_same_v<T, empty>) os << ":" << cost; os << ')'; } }; template <class T> struct _Edges : public std::vector<_Edge<T>> { using std::vector<_Edge<T>>::vector; template <class IStream, is_istream_t<IStream> * = nullptr> _Edges &input(IStream &is, bool is_one_indexed = false) { for (int i = 0; i < (int)this->size(); i++) { int u, v; T w{}; is >> u >> v; if (is_one_indexed) --u, --v; if constexpr (!std::is_same_v<T, empty>) is >> w; (*this)[i] = _Edge<T>(v, w, u, i); } return *this; } template <class IStream, is_istream_t<IStream> * = nullptr> friend _Edges &input(_Edges &edges, IStream &is, bool is_one_indexed = false) { return edges.input(is, is_one_indexed); } template <class OStream, is_ostream_t<OStream> * = nullptr> void debug_output(OStream &os) const { os << '['; for (int i = 0; i < (int)this->size(); i++) { if (i) os << ", "; (*this)[i].debug_output(os); } os << ']'; } _Edges &add_edge(int from, int to, T cost = T{}) { this->emplace_back(to, cost, from, this->size()); return *this; } friend _Edges &add_edge(_Edges &edges, int from, int to, T cost = T{}) { edges.emplace_back(to, cost, from, edges.size()); return edges; } }; template <class T> struct _pair { T cost; int id; _pair(T cost_, int id_) : cost(cost_), id(id_) {} _pair() : cost(), id(-1) {} operator bool() const { return id != -1; } template <class OStream, is_ostream_t<OStream> * = nullptr> friend OStream &operator<<(OStream &os, const _pair &p) { if constexpr (std::is_same_v<T, empty>) return os; else return os << p.cost; } }; template <class T> using _pairs = std::vector<_pair<T>>; } // namespace graph template <typename T> using WEdge = graph::_Edge<T>; template <typename T> using WEdges = graph::_Edges<T>; using Edge = graph::_Edge<graph::empty>; using Edges = graph::_Edges<graph::empty>; } // namespace kk2 #endif // KK2_GRAPH_EDGE_HPP namespace kk2 { namespace graph { template <class T, bool is_directed> struct AdjacencyList { using value_type = T; using out_edge_type = _Edge<T>; using out_edges = _Edges<T>; using adjacency_container = std::vector<out_edges>; using edge_type = _Edge<T>; using edge_collection = _Edges<T>; static constexpr bool directed = is_directed; static constexpr bool weighted = !std::is_same_v<T, empty>; static constexpr bool adjacency_list = true; static constexpr bool adjacency_matrix = false; static constexpr bool static_graph = false; adjacency_container data; edge_collection edges; AdjacencyList() = default; AdjacencyList(int n_) : data(n_) {} // input を使うことが前提 AdjacencyList(int n_, int m_) : data(n_), edges(m_) {} AdjacencyList(int n_, const edge_collection &edges_) : data(n_), edges(edges_.size()) { for (auto &&e : edges_) _add_edge<true>(e.from, e.to, e.cost, e.id); } inline int num_vertices() const { return data.size(); } inline int size() const { return data.size(); } inline int num_edges() const { return edges.size(); } out_edges &operator[](int k) { return data[k]; } const out_edges &operator[](int k) const { return data[k]; } void edge_clear() { *this = AdjacencyList(num_vertices()); } void add_edge(int from, int to, T cost = T{}) { _add_edge<false>(from, to, cost, num_edges()); } void add_vertex(int n = 1) { data.insert(data.end(), n, out_edges()); } template <class IStream, is_istream_t<IStream> * = nullptr> AdjacencyList &input(IStream &is, bool oneindexed = false) { for (int i = 0; i < num_edges(); i++) { int u, v; T w{}; is >> u >> v; if constexpr (weighted) is >> w; if (oneindexed) --u, --v; _add_edge<true>(u, v, w, i); } return *this; } template <class OStream, is_ostream_t<OStream> * = nullptr> void debug_output(OStream &os) const { os << "[\n"; for (int i = 0; i < num_vertices(); i++) { os << " " << i << ": ["; for (size_t j = 0; j < data[i].size(); j++) { if (j) os << ", "; data[i][j].debug_output(os); } os << "]\n"; } os << "]\n"; } private: template <bool update = false> void _add_edge(int from, int to, T cost, int id) { data[from].emplace_back(to, cost, from, id); if (!is_directed and from != to) data[to].emplace_back(from, cost, to, id); if constexpr (update) edges[id] = edge_type(to, cost, from, id); else edges.emplace_back(to, cost, from, id); } public: AdjacencyList reverse() const { AdjacencyList res(num_vertices(), num_edges()); for (auto &&e : edges) res._add_edge<true>(e.to, e.from, e.cost, e.id); return res; } }; template <class T, bool is_directed> struct AdjacencyMatrix { using value_type = T; using out_edge_type = _pair<T>; using out_edges = _pairs<T>; using adjacency_container = std::vector<out_edges>; using edge_type = _Edge<T>; using edge_collection = _Edges<T>; static constexpr bool directed = is_directed; static constexpr bool weighted = !std::is_same_v<T, empty>; static constexpr bool adjacency_list = false; static constexpr bool adjacency_matrix = true; static constexpr bool static_graph = false; adjacency_container data; edge_collection edges; AdjacencyMatrix() = default; AdjacencyMatrix(int n_) : data(n_, out_edges(n_)) {} // input を使うことが前提 AdjacencyMatrix(int n_, int m_) : data(n_, out_edges(n_)), edges(m_) {} AdjacencyMatrix(int n_, const edge_collection &edges_) : data(n_, out_edges(n_)), edges(edges_.size()) { for (auto &&e : edges_) _add_edge<true>(e.from, e.to, e.cost, e.id); } inline int num_vertices() const { return data.size(); } inline int size() const { return data.size(); } inline int num_edges() const { return edges.size(); } out_edges &operator[](int k) { return data[k]; } const out_edges &operator[](int k) const { return data[k]; } void edge_clear() { *this = AdjacencyMatrix(num_vertices()); } void add_edge(int from, int to, T cost = T{}) { _add_edge<false>(from, to, cost, num_edges()); } void add_vertex(int n = 1) { int now = num_vertices(); data.resize(now + n); for (auto &&d : data) d.resize(now + n); } template <class IStream, is_istream_t<IStream> * = nullptr> AdjacencyMatrix &input(IStream &is, bool oneindexed = false) { for (int i = 0; i < num_edges(); i++) { int u, v; T w{}; is >> u >> v; if constexpr (weighted) is >> w; if (oneindexed) --u, --v; _add_edge<true>(u, v, w, i); } return *this; } template <class OStream, is_ostream_t<OStream> * = nullptr> void debug_output(OStream &os) const { os << "[\n"; for (int i = 0; i < num_vertices(); i++) { os << " " << i << ": ["; for (size_t j = 0; j < data[i].size(); j++) { if (j) os << ", "; os << "(" << data[i][j].id << ", " << i << "->" << j; if constexpr (weighted) os << ": " << data[i][j].cost; os << ")"; } os << "]\n"; } os << "]\n"; } private: template <bool update = false> void _add_edge(int from, int to, T cost, int id) { data[from][to] = out_edge_type(cost, id); if constexpr (!is_directed) data[to][from] = out_edge_type(cost, id); if constexpr (update) edges[id] = edge_type(to, cost, from, id); else edges.emplace_back(to, cost, from, id); } public: AdjacencyMatrix reverse() const { AdjacencyMatrix res(num_vertices(), num_edges()); for (auto &&e : edges) res._add_edge<true>(e.to, e.from, e.cost, e.id); return res; } }; } // namespace graph template <typename T> using WAdjList = graph::AdjacencyList<T, false>; template <typename T> using DWAdjList = graph::AdjacencyList<T, true>; using AdjList = graph::AdjacencyList<graph::empty, false>; using DAdjList = graph::AdjacencyList<graph::empty, true>; template <typename T> using WAdjMat = graph::AdjacencyMatrix<T, false>; template <typename T> using DWAdjMat = graph::AdjacencyMatrix<T, true>; using AdjMat = graph::AdjacencyMatrix<graph::empty, false>; using DAdjMat = graph::AdjacencyMatrix<graph::empty, true>; } // namespace kk2 #endif // KK2_GRAPH_GRAPH_HPP using namespace std; void solve() { /* 最小カットに言い換え Pが負なら,とったときに,-Pの損失 Pが正なら,とらなかったときに,Pの損失 があると,いい感じにオフセットをとる */ int n; kin >> n; vc<int> p(n); kin >> p; int m; kin >> m; vc<pi> uv(m); kin >> uv; rep (i, m) uv[i].first--, uv[i].second--; int k; kin >> k; vc<array<int, 3>> ab(k); kin >> ab; rep (i, k) ab[i][0]--, ab[i][1]--; kk2::DWAdjList<i64> g(n + k + 2); int s = n + k, t = n + k + 1; i64 off = 0; rep (i, n) { if (p[i] > 0) { g.add_edge(s, i, 0); g.add_edge(i, t, p[i]); off += p[i]; } else { g.add_edge(s, i, -p[i]); g.add_edge(i, t, 0); } } rep (i, m) { auto [u, v] = uv[i]; g.add_edge(u, v, 1e12); } rep (i, k) { auto [a, b, ss] = ab[i]; g.add_edge(s, n + i, 0); g.add_edge(n + i, t, ss); g.add_edge(a, n + i, 1e12); g.add_edge(b, n + i, 1e12); off += ss; } kk2::MaxFlow mf(g); i64 flow = mf.flow(s, t); kout << off - flow << "\n"; } int main() { #ifdef KK2 int t = 2; #else int t = 1; #endif // kin >> t; rep (t) solve(); return 0; } // Author: kk2 // converted by https://github.com/kk2a/cpp-bundle // 2025-07-12 18:40:46