#include #include #include namespace suisen { // ! utility template using constraints_t = std::enable_if_t, std::nullptr_t>; template constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) { if constexpr (cond_v) { return std::forward(then); } else { return std::forward(or_else); } } // ! function template using is_same_as_invoke_result = std::is_same, ReturnType>; template using is_uni_op = is_same_as_invoke_result; template using is_bin_op = is_same_as_invoke_result; template using is_comparator = std::is_same, bool>; // ! integral template >> constexpr int bit_num = std::numeric_limits>::digits; template struct is_nbit { static constexpr bool value = bit_num == n; }; template static constexpr bool is_nbit_v = is_nbit::value; // ? template struct safely_multipliable {}; template <> struct safely_multipliable { using type = long long; }; template <> struct safely_multipliable { using type = __int128_t; }; template <> struct safely_multipliable { using type = unsigned long long; }; template <> struct safely_multipliable { using type = __uint128_t; }; template <> struct safely_multipliable { using type = __uint128_t; }; template <> struct safely_multipliable { using type = float; }; template <> struct safely_multipliable { using type = double; }; template <> struct safely_multipliable { using type = long double; }; template using safely_multipliable_t = typename safely_multipliable::type; } // namespace suisen // ! type aliases using i128 = __int128_t; using u128 = __uint128_t; template using pq_greater = std::priority_queue, std::greater>; template using umap = std::unordered_map; // ! macros (capital: internal macro) #define OVERLOAD2(_1,_2,name,...) name #define OVERLOAD3(_1,_2,_3,name,...) name #define OVERLOAD4(_1,_2,_3,_4,name,...) name #define REP4(i,l,r,s) for(std::remove_reference_t>i=(l);i<(r);i+=(s)) #define REP3(i,l,r) REP4(i,l,r,1) #define REP2(i,n) REP3(i,0,n) #define REPINF3(i,l,s) for(std::remove_reference_t>i=(l);;i+=(s)) #define REPINF2(i,l) REPINF3(i,l,1) #define REPINF1(i) REPINF2(i,0) #define RREP4(i,l,r,s) for(std::remove_reference_t>i=(l)+fld((r)-(l)-1,s)*(s);i>=(l);i-=(s)) #define RREP3(i,l,r) RREP4(i,l,r,1) #define RREP2(i,n) RREP3(i,0,n) #define rep(...) OVERLOAD4(__VA_ARGS__, REP4 , REP3 , REP2 )(__VA_ARGS__) #define rrep(...) OVERLOAD4(__VA_ARGS__, RREP4 , RREP3 , RREP2 )(__VA_ARGS__) #define repinf(...) OVERLOAD3(__VA_ARGS__, REPINF3, REPINF2, REPINF1)(__VA_ARGS__) #define CAT_I(a, b) a##b #define CAT(a, b) CAT_I(a, b) #define UNIQVAR(tag) CAT(tag, __LINE__) #define loop(n) for (std::remove_reference_t> UNIQVAR(loop_variable) = n; UNIQVAR(loop_variable) --> 0;) #define all(iterable) std::begin(iterable), std::end(iterable) #define input(type, ...) type __VA_ARGS__; read(__VA_ARGS__) #ifdef LOCAL # define debug(...) debug_internal(#__VA_ARGS__, __VA_ARGS__) template void debug_internal(const char* s, T&& first, Args&&... args) { constexpr const char* prefix = "[\033[32mDEBUG\033[m] "; constexpr const char* open_brakets = sizeof...(args) == 0 ? "" : "("; constexpr const char* close_brakets = sizeof...(args) == 0 ? "" : ")"; std::cerr << prefix << open_brakets << s << close_brakets << ": " << open_brakets << std::forward(first); ((std::cerr << ", " << std::forward(args)), ...); std::cerr << close_brakets << "\n"; } #else # define debug(...) void(0) #endif // ! I/O utilities // pair template std::ostream& operator<<(std::ostream& out, const std::pair &a) { return out << a.first << ' ' << a.second; } // tuple template std::ostream& operator<<(std::ostream& out, const std::tuple &a) { if constexpr (N >= std::tuple_size_v>) { return out; } else { out << std::get(a); if constexpr (N + 1 < std::tuple_size_v>) { out << ' '; } return operator<<(out, a); } } // vector template std::ostream& operator<<(std::ostream& out, const std::vector &a) { for (auto it = a.begin(); it != a.end();) { out << *it; if (++it != a.end()) out << ' '; } return out; } // array template std::ostream& operator<<(std::ostream& out, const std::array &a) { for (auto it = a.begin(); it != a.end();) { out << *it; if (++it != a.end()) out << ' '; } return out; } inline void print() { std::cout << '\n'; } template inline void print(const Head &head, const Tail &...tails) { std::cout << head; if (sizeof...(tails)) std::cout << ' '; print(tails...); } template auto print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") -> decltype(std::cout << *v.begin(), void()) { for (auto it = v.begin(); it != v.end();) { std::cout << *it; if (++it != v.end()) std::cout << sep; } std::cout << end; } // pair template std::istream& operator>>(std::istream& in, std::pair &a) { return in >> a.first >> a.second; } // tuple template std::istream& operator>>(std::istream& in, std::tuple &a) { if constexpr (N >= std::tuple_size_v>) { return in; } else { return operator>>(in >> std::get(a), a); } } // vector template std::istream& operator>>(std::istream& in, std::vector &a) { for (auto it = a.begin(); it != a.end(); ++it) in >> *it; return in; } // array template std::istream& operator>>(std::istream& in, std::array &a) { for (auto it = a.begin(); it != a.end(); ++it) in >> *it; return in; } template void read(Args &...args) { ( std::cin >> ... >> args ); } // ! integral utilities // Returns pow(-1, n) template constexpr inline int pow_m1(T n) { return -(n & 1) | 1; } // Returns pow(-1, n) template <> constexpr inline int pow_m1(bool n) { return -int(n) | 1; } // Returns floor(x / y) template constexpr inline T fld(const T x, const T y) { return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y; } template constexpr inline T cld(const T x, const T y) { return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y; } template > = nullptr> constexpr inline int popcount(const T x) { return __builtin_popcount(x); } template > = nullptr> constexpr inline int popcount(const T x) { return __builtin_popcount(x); } template > = nullptr> constexpr inline int popcount(const T x) { return __builtin_popcountll(x); } template > = nullptr> constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_lz(const T x) { return x ? __builtin_clzll(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num; } template > = nullptr> constexpr inline int count_tz(const T x) { return x ? __builtin_ctzll(x) : suisen::bit_num; } template constexpr inline int floor_log2(const T x) { return suisen::bit_num - 1 - count_lz(x); } template constexpr inline int ceil_log2(const T x) { return floor_log2(x) + ((x & -x) != x); } template constexpr inline int kth_bit(const T x, const unsigned int k) { return (x >> k) & 1; } template constexpr inline int parity(const T x) { return popcount(x) & 1; } struct all_subset { struct all_subset_iter { const int s; int t; constexpr all_subset_iter(int s) : s(s), t(s + 1) {} constexpr auto operator*() const { return t; } constexpr auto operator++() {} constexpr auto operator!=(std::nullptr_t) { return t ? (--t &= s, true) : false; } }; int s; constexpr all_subset(int s) : s(s) {} constexpr auto begin() { return all_subset_iter(s); } constexpr auto end() { return nullptr; } }; // ! container template > = nullptr> auto priqueue_comp(const Comparator comparator) { return std::priority_queue, Comparator>(comparator); } template auto isize(const Iterable &iterable) -> decltype(int(iterable.size())) { return iterable.size(); } template > = nullptr> auto generate_vector(int n, Gen generator) { std::vector v(n); for (int i = 0; i < n; ++i) v[i] = generator(i); return v; } template auto generate_range_vector(T l, T r) { return generate_vector(r - l, [l](int i) { return l + i; }); } template auto generate_range_vector(T n) { return generate_range_vector(0, n); } template void sort_unique_erase(std::vector &a) { std::sort(a.begin(), a.end()); a.erase(std::unique(a.begin(), a.end()), a.end()); } template auto foreach_adjacent_values(InputIterator first, InputIterator last, BiConsumer f) -> decltype(f(*first++, *last), void()) { if (first != last) for (auto itr = first, itl = itr++; itr != last; itl = itr++) f(*itl, *itr); } template auto foreach_adjacent_values(Container c, BiConsumer f) -> decltype(c.begin(), c.end(), void()){ foreach_adjacent_values(c.begin(), c.end(), f); } // ! other utilities // x <- min(x, y). returns true iff `x` has chenged. template inline bool chmin(T &x, const T &y) { if (y >= x) return false; x = y; return true; } // x <- max(x, y). returns true iff `x` has chenged. template inline bool chmax(T &x, const T &y) { if (y <= x) return false; x = y; return true; } namespace suisen {} using namespace suisen; using namespace std; struct io_setup { io_setup(int precision = 20) { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::fixed << std::setprecision(precision); } } io_setup_ {}; // ! code from here #include #include // l <= x < r template constexpr inline bool in_range(const T &x, const T &l, const T &r) { return l <= x and x < r; } // 0 <= x < r template constexpr inline bool in_range(const T &x, const T &r) { return (std::make_unsigned_t) x < (std::make_unsigned_t) r; } // not (l <= x < r) template constexpr inline bool out_range(const T &x, const T &l, const T &r) { return x < l or r <= x; } // not (0 <= x < r) template constexpr inline bool out_range(const T &x, const T &r) { return (std::make_unsigned_t) x >= (std::make_unsigned_t) r; } constexpr int dx4[4] = {1, 0, -1, 0}; constexpr int dy4[4] = {0, 1, 0, -1}; constexpr int dx8[8] = {1, 1, 0, -1, -1, -1, 0, 1}; constexpr int dy8[8] = {0, 1, 1, 1, 0, -1, -1, -1}; constexpr std::pair dxy4[4] = { { dx4[0], dy4[0] }, { dx4[1], dy4[1] }, { dx4[2], dy4[2] }, { dx4[3], dy4[3] }, }; constexpr std::pair dxy8[8] = { { dx8[0], dy8[0] }, { dx8[1], dy8[1] }, { dx8[2], dy8[2] }, { dx8[3], dy8[3] }, { dx8[4], dy8[4] }, { dx8[5], dy8[5] }, { dx8[6], dy8[6] }, { dx8[7], dy8[7] }, }; template struct AdjacentCells { struct Iterator { const int x, y; int d; bool operator!=(std::nullptr_t) { return d != D; } void operator++() { ++d; } std::pair operator*() { return { x + dx[d], y + dy[d] }; } }; const int x, y; AdjacentCells(int x, int y) : x(x), y(y) {} auto begin() { return Iterator { x, y, 0 }; } constexpr std::nullptr_t end() { return nullptr; } operator std::vector>() { std::vector> res; for (const auto &p : *this) res.push_back(p); return res; } }; template struct AdjacentCellsBounded { struct Iterator { const int x, y, xl, xr, yl, yr; int d; bool operator!=(std::nullptr_t) { for (; d != D; ++d) if (in_range(x + dx[d], xl, xr) and in_range(y + dy[d], yl, yr)) return true; return false; } void operator++() { ++d; } std::pair operator*() { return { x + dx[d], y + dy[d] }; } }; const int x, y, xl, xr, yl, yr; AdjacentCellsBounded(int x, int y, int xl, int xr, int yl, int yr) : x(x), y(y), xl(xl), xr(xr), yl(yl), yr(yr) {} AdjacentCellsBounded(int x, int y, int xr, int yr) : AdjacentCellsBounded(x, y, 0, xr, 0, yr) {} auto begin() { return Iterator { x, y, xl, xr, yl, yr, 0 }; } constexpr std::nullptr_t end() { return nullptr; } operator std::vector>() { std::vector> res; for (const auto &p : *this) res.push_back(p); return res; } }; // [ {x+dx4[i], y+dy4[i]} for i in range(4) ] using AdjacentFourCells = AdjacentCells<4, dx4, dy4>; // [ {nx:=x+dx4[i], ny:=y+dy4[i]} for i in range(4) if xl<=nx; // [ {x+dx8[i], y+dy8[i]} for i in range(8) ] using AdjacentEightCells = AdjacentCells<8, dx8, dy8>; // [ {nx:=x+dx8[i], ny:=y+dy8[i]} for i in range(8) if xl<=nx; // [ {x+dx4[i], y+dy4[i]} for i in range(4) ] auto adjacent_four_cells(int x, int y) { return AdjacentFourCells { x, y }; } // [ {nx:=x+dx4[i], ny:=y+dy4[i]} for i in range(4) if xl<=nx(w)); read(a); vector vis(h, vector(w, false)); vis[sx][sy] = true; long long cur = a[sx][sy]; pq_greater> pq; for (auto [nx, ny] : adjacent_four_cells(sx, sy, h, w)) { pq.emplace(a[nx][ny], nx, ny); vis[nx][ny] = true; } while (pq.size()) { auto [atk, cx, cy] = pq.top(); pq.pop(); if (atk >= cur) { print("No"); return 0; } cur += atk; for (auto [nx, ny] : adjacent_four_cells(cx, cy, h, w)) { if (vis[nx][ny]) continue; pq.emplace(a[nx][ny], nx, ny); vis[nx][ny] = true; } } print("Yes"); return 0; }