結果
問題 | No.2155 みちらcolor |
ユーザー | KowerKoint2010 |
提出日時 | 2022-12-01 09:22:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 37,078 bytes |
コンパイル時間 | 2,264 ms |
コンパイル使用メモリ | 232,740 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-14 18:50:51 |
合計ジャッジ時間 | 3,691 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 1 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 2 ms
5,248 KB |
testcase_17 | AC | 1 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 1 ms
5,248 KB |
testcase_20 | AC | 2 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 1 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 2 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
testcase_30 | AC | 2 ms
5,248 KB |
testcase_31 | AC | 2 ms
5,248 KB |
testcase_32 | AC | 2 ms
5,248 KB |
testcase_33 | AC | 1 ms
5,248 KB |
testcase_34 | AC | 1 ms
5,248 KB |
testcase_35 | AC | 2 ms
5,248 KB |
testcase_36 | AC | 2 ms
5,248 KB |
testcase_37 | AC | 2 ms
5,248 KB |
testcase_38 | AC | 2 ms
5,248 KB |
testcase_39 | AC | 2 ms
5,248 KB |
testcase_40 | AC | 1 ms
5,248 KB |
testcase_41 | AC | 2 ms
5,248 KB |
testcase_42 | AC | 2 ms
5,248 KB |
testcase_43 | AC | 2 ms
5,248 KB |
testcase_44 | AC | 1 ms
5,248 KB |
testcase_45 | AC | 2 ms
5,248 KB |
testcase_46 | AC | 2 ms
5,248 KB |
testcase_47 | AC | 2 ms
5,248 KB |
testcase_48 | AC | 2 ms
5,248 KB |
testcase_49 | AC | 2 ms
5,248 KB |
testcase_50 | AC | 2 ms
5,248 KB |
testcase_51 | AC | 2 ms
5,248 KB |
testcase_52 | AC | 2 ms
5,248 KB |
testcase_53 | AC | 1 ms
5,248 KB |
testcase_54 | AC | 1 ms
5,248 KB |
testcase_55 | AC | 2 ms
5,248 KB |
testcase_56 | AC | 2 ms
5,248 KB |
testcase_57 | AC | 2 ms
5,248 KB |
testcase_58 | AC | 2 ms
5,248 KB |
testcase_59 | AC | 2 ms
5,248 KB |
testcase_60 | AC | 2 ms
5,248 KB |
testcase_61 | AC | 2 ms
5,248 KB |
testcase_62 | AC | 2 ms
5,248 KB |
testcase_63 | AC | 1 ms
5,248 KB |
testcase_64 | AC | 2 ms
5,248 KB |
testcase_65 | AC | 2 ms
5,248 KB |
testcase_66 | AC | 2 ms
5,248 KB |
ソースコード
#line 2 "library/KowerKoint/base.hpp" #include <bits/stdc++.h> using namespace std; #line 4 "library/KowerKoint/stl-wrapper/pair.hpp" template <typename T1, typename T2> struct Pair : public std::pair<T1, T2> { constexpr Pair() : std::pair<T1, T2>() {} constexpr Pair(const T1& first, const T2& second) : std::pair<T1, T2>(first, second) {} template <typename U1, typename U2> constexpr Pair(U1&& first, U2&& second) : std::pair<T1, T2>(std::forward<U1>(first), std::forward<U2>(second)) {} template <typename U1, typename U2> constexpr Pair(const std::pair<U1, U2>& other) : std::pair<T1, T2>(other) {} template <typename U1, typename U2> constexpr Pair(std::pair<U1, U2>&& other) : std::pair<T1, T2>(std::move(other)) {} template <typename... Args1, typename... Args2> Pair(std::piecewise_construct_t, std::tuple<Args1...> first_args, std::tuple<Args2...> second_args) : std::pair<T1, T2>(std::piecewise_construct, first_args, second_args) {} friend std::istream& operator>>(std::istream& is, Pair& p) { return is >> p.first >> p.second; } friend std::ostream& operator<<(std::ostream& os, const Pair& p) { return os << p.first << ' ' << p.second; } }; namespace std { template <typename T1, typename T2> struct hash<Pair<T1, T2>> { size_t operator()(const Pair<T1, T2>& p) const { size_t seed = 0; seed ^= hash<T1>()(p.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash<T2>()(p.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; } #line 5 "library/KowerKoint/stl-wrapper/vector.hpp" template <typename T> struct Vector : std::vector<T> { Vector() noexcept : std::vector<T>() {} explicit Vector(size_t count) : std::vector<T>(count, T()) {} Vector(size_t count, const T& value) : std::vector<T>(count, value) {} template <typename InputIt> Vector(InputIt first, InputIt last) : std::vector<T>(first, last) {} Vector(const std::vector<T>& other) : std::vector<T>(other) {} Vector(std::vector<T>&& other) noexcept : std::vector<T>(std::move(other)) {} Vector(std::initializer_list<T> init) : std::vector<T>(init) {} const T& operator[](size_t i) const { assert(i < this->size()); return std::vector<T>::operator[](i); } T& operator[](size_t i) { assert(i < this->size()); return std::vector<T>::operator[](i); } const T& front() const { assert(!this->empty()); return std::vector<T>::front(); } T& front() { assert(!this->empty()); return std::vector<T>::front(); } const T& back() const { assert(!this->empty()); return std::vector<T>::back(); } T& back() { assert(!this->empty()); return std::vector<T>::back(); } friend std::istream& operator>>(std::istream& is, Vector& v) { for (auto& x : v) is >> x; return is; } friend std::ostream& operator<<(std::ostream& os, const Vector& v) { for (size_t i = 0; i < v.size(); ++i) { if (i) os << ' '; os << v[i]; } return os; } }; namespace std { template <typename T> struct hash<Vector<T>> { size_t operator()(const Vector<T>& v) const { size_t seed = 0; for (const auto& x : v) seed ^= hash<T>{}(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; }; #line 4 "library/KowerKoint/stl-wrapper/set.hpp" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #line 7 "library/KowerKoint/stl-wrapper/set.hpp" template <typename T, typename Compare = std::less<T>> using pbds_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; template <typename T, typename Compare = std::less<T>> struct Set : public pbds_set<T, Compare> { Set() : pbds_set<T, Compare>() {} explicit Set(const Compare& comp) : pbds_set<T, Compare>(comp) {} template <typename It> Set(It first, It last, const Compare& comp = Compare()) : pbds_set<T, Compare>(first, last, comp) {} Set(const pbds_set<T, Compare>& other) : pbds_set<T, Compare>(other) {} Set(const std::set<T, Compare>& other) : pbds_set<T, Compare>(other.begin(), other.end()) {} Set(pbds_set<T, Compare>&& other) : pbds_set<T, Compare>(std::move(other)) {} Set(std::initializer_list<T> init, const Compare& comp = Compare()) : pbds_set<T, Compare>(init, comp) {} typename Set::const_iterator cbegin() const { return this->begin(); } typename Set::const_iterator cend() const { return this->end(); } typename Set::const_reverse_iterator crbegin() const { return this->rbegin(); } typename Set::const_reverse_iterator crend() const { return this->rend(); } template <typename K> std::pair<typename Set::iterator, typename Set::iterator> equal_range(const K& value) { return std::make_pair(lower_bound(value), upper_bound(value)); } template <typename K> std::pair<typename Set::const_iterator, typename Set::const_iterator> equal_range(const K& value) const { return std::make_pair(lower_bound(value), upper_bound(value)); } template <typename K> size_t count(const K& x) const { return this->find(x) != this->end(); } decltype(Compare()) key_comp() const { return Compare(); } template <typename... Args> std::pair<typename Set::iterator, bool> emplace(Args&&... args) { return this->insert(T(std::forward<Args>(args)...)); } template <typename... Args> typename Set::iterator emplace_hint(typename Set::const_iterator hint, Args&&... args) { return this->insert(hint, T(std::forward<Args>(args)...)); } friend std::ostream& operator<<(std::ostream& os, const Set& set) { Vector<T> vector(set.begin(), set.end()); return os << vector; } }; namespace _set_util { template <typename T, typename Compare> struct CompareEqual { bool operator()(const T& lhs, const T& rhs) const { return !Compare()(rhs, lhs); } }; } template <typename T, typename Compare = std::less<T>> using pbds_multiset = __gnu_pbds::tree<T, __gnu_pbds::null_type, _set_util::CompareEqual<T, Compare>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; template <typename T, typename Compare = std::less<T>> struct MultiSet : public pbds_multiset<T, Compare> { MultiSet() : pbds_multiset<T, Compare>() {} explicit MultiSet(const Compare& comp) : pbds_multiset<T, Compare>(comp) {} template <typename It> MultiSet(It first, It last, const Compare& comp = Compare()) : pbds_multiset<T, Compare>(first, last, comp) {} MultiSet(const pbds_multiset<T, Compare>& other) : pbds_multiset<T, Compare>(other) {} MultiSet(const std::multiset<T, Compare>& other) : pbds_multiset<T, Compare>(other.begin(), other.end()) {} MultiSet(pbds_multiset<T, Compare>&& other) : pbds_multiset<T, Compare>(std::move(other)) {} MultiSet(std::initializer_list<T> init, const Compare& comp = Compare()) : pbds_multiset<T, Compare>(init, comp) {} typename MultiSet::const_iterator cbegin() const { return this->begin(); } typename MultiSet::const_iterator cend() const { return this->end(); } typename MultiSet::const_reverse_iterator crbegin() const { return this->rbegin(); } typename MultiSet::const_reverse_iterator crend() const { return this->rend(); } template <typename K> std::pair<typename MultiSet::iterator, typename MultiSet::iterator> equal_range(const K& value) { return std::make_pair(lower_bound(value), upper_bound(value)); } template <typename K> std::pair<typename MultiSet::const_iterator, typename MultiSet::const_iterator> equal_range(const K& value) const { return std::make_pair(lower_bound(value), upper_bound(value)); } template <typename K> size_t count(const K& x) const { auto range = equal_range(x); return std::distance(range.first, range.second); } decltype(Compare()) key_comp() const { return Compare(); } template <typename... Args> typename MultiSet::iterator emplace(Args&&... args) { return this->insert(T(std::forward<Args>(args)...)); } template <typename... Args> typename MultiSet::iterator emplace_hint(typename MultiSet::const_iterator hint, Args&&... args) { return this->insert(hint, T(std::forward<Args>(args)...)); } friend std::ostream& operator<<(std::ostream& os, const MultiSet& set) { Vector<T> vector(set.begin(), set.end()); return os << vector; } }; namespace std { template <typename T, typename Compare> struct hash<Set<T, Compare>> { size_t operator()(const Set<T, Compare>& set) const { Vector<T> vec(set.begin(), set.end()); return hash<Vector<T>>()(vec); } }; template <typename T, typename Compare> struct hash<MultiSet<T, Compare>> { size_t operator()(const MultiSet<T, Compare>& set) const { Vector<T> vec(set.begin(), set.end()); return hash<Vector<T>>()(vec); } }; }; #line 7 "library/KowerKoint/stl-wrapper/map.hpp" template <typename Key, typename Value, typename Compare> using pbds_map = __gnu_pbds::tree<Key, Value, Compare, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; template <typename Key, typename Value, typename Compare = std::less<Key>> struct Map : pbds_map<Key, Value, Compare> { Map() : pbds_map<Key, Value, Compare>() {} explicit Map(const Compare& comp) : pbds_map<Key, Value, Compare>(comp) {} template <typename It> Map(It first, It last, const Compare& comp = Compare()) : pbds_map<Key, Value, Compare>(first, last, comp) {} Map(const pbds_map<Key, Value, Compare>& other) : pbds_map<Key, Value, Compare>(other) {} Map(const std::map<Key, Value, Compare>& other) : pbds_map<Key, Value, Compare>(other.begin(), other.end()) {} Map(pbds_map<Key, Value, Compare>&& other) : pbds_map<Key, Value, Compare>(std::move(other)) {} Map(std::initializer_list<std::pair<Key, Value>> init, const Compare& comp = Compare()) : pbds_map<Key, Value, Compare>(init, comp) {} typename Map::const_iterator cbegin() const { return this->begin(); } typename Map::const_iterator cend() const { return this->end(); } typename Map::const_reverse_iterator crbegin() const { return this->rbegin(); } typename Map::const_reverse_iterator crend() const { return this->rend(); } template <typename K> std::pair<typename Map::iterator, typename Map::iterator> equal_range(const K& value) { return std::make_pair(lower_bound(value), upper_bound(value)); } template <typename K> std::pair<typename Map::const_iterator, typename Map::const_iterator> equal_range(const K& value) const { return std::make_pair(lower_bound(value), upper_bound(value)); } Value& at(const Key& key) { auto it = find(key); assert(it != this->end()); return it->second; } const Value& at(const Key& key) const { auto it = find(key); assert(it != this->end()); return it->second; } template <typename K> size_t count(const K& x) const { return this->find(x) != this->end(); } decltype(Compare()) key_comp() const { return Compare(); } template <typename... Args> std::pair<typename Map::iterator, bool> emplace(Args&&... args) { return this->insert(std::make_pair(std::forward<Args>(args)...)); } template <typename... Args> typename Map::iterator emplace_hint(typename Map::const_iterator hint, Args&&... args) { return this->insert(hint, std::make_pair(std::forward<Args>(args)...)); } friend std::ostream& operator<<(std::ostream& out, const Map& map) { for (auto it = map.begin(); it != map.end(); ++it) { out << it->first << ' ' << it->second << '\n'; } return out; } }; namespace _map_util { template <typename T, typename Compare> struct CompareEqual { bool operator()(const T& lhs, const T& rhs) const { return !Compare()(rhs, lhs); } }; } template <typename Key, typename Value, typename Compare = std::less<Key>> using pbds_multimap = __gnu_pbds::tree<Key, Value, _map_util::CompareEqual<Key, Compare>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; template <typename Key, typename Value, typename Compare = std::less<Key>> struct MultiMap : pbds_multimap<Key, Value, Compare> { MultiMap() : pbds_multimap<Key, Value, Compare>() {} explicit MultiMap(const Compare& comp) : pbds_multimap<Key, Value, Compare>(comp) {} template <typename It> MultiMap(It first, It last, const Compare& comp = Compare()) : pbds_multimap<Key, Value, Compare>(first, last, comp) {} MultiMap(const pbds_multimap<Key, Value, Compare>& other) : pbds_multimap<Key, Value, Compare>(other) {} MultiMap(const std::multimap<Key, Value, Compare>& other) : pbds_multimap<Key, Value, Compare>(other.begin(), other.end()) {} MultiMap(pbds_multimap<Key, Value, Compare>&& other) : pbds_multimap<Key, Value, Compare>(std::move(other)) {} MultiMap(std::initializer_list<std::pair<Key, Value>> init, const Compare& comp = Compare()) : pbds_multimap<Key, Value, Compare>(init, comp) {} typename MultiMap::const_iterator cbegin() const { return this->begin(); } typename MultiMap::const_iterator cend() const { return this->end(); } typename MultiMap::const_reverse_iterator crbegin() const { return this->rbegin(); } typename MultiMap::const_reverse_iterator crend() const { return this->rend(); } template <typename K> std::pair<typename MultiMap::iterator, typename MultiMap::iterator> equal_range(const K& value) { return std::make_pair(lower_bound(value), upper_bound(value)); } template <typename K> std::pair<typename MultiMap::const_iterator, typename MultiMap::const_iterator> equal_range(const K& value) const { return std::make_pair(lower_bound(value), upper_bound(value)); } Value& at(const Key& key) { auto it = find(key); assert(it != this->end()); return it->second; } const Value& at(const Key& key) const { auto it = find(key); assert(it != this->end()); return it->second; } template <typename K> size_t count(const K& x) const { auto range = equal_range(x); return std::distance(range.first, range.second); } decltype(Compare())key_comp() const { return Compare(); } template <typename... Args> typename MultiMap::iterator emplace(Args&&... args) { return this->insert(std::make_pair(std::forward<Args>(args)...)); } template <typename... Args> typename MultiMap::iterator emplace_hint(typename MultiMap::const_iterator hint, Args&&... args) { return this->insert(hint, std::make_pair(std::forward<Args>(args)...)); } friend std::ostream& operator<<(std::ostream& out, const MultiMap& map) { for (auto it = map.begin(); it != map.end(); ++it) { out << it->first << ' ' << it->second << '\n'; } return out; } }; namespace std { template <typename Key, typename Value, typename Compare> struct hash<Map<Key, Value, Compare>> { size_t operator()(const Map<Key, Value, Compare>& map) const { Vector<pair<Key, Value>> v(map.begin(), map.end()); return hash<Vector<pair<Key, Value>>>()(v); } }; template <typename Key, typename Value, typename Compare> struct hash<MultiMap<Key, Value, Compare>> { size_t operator()(const Map<Key, Value, Compare>& map) const { Vector<pair<Key, Value>> v(map.begin(), map.end()); return hash<Vector<pair<Key, Value>>>()(v); } }; } #line 9 "library/KowerKoint/stl-wrapper/unordered_set.hpp" template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>> using pbds_unordered_set = __gnu_pbds::gp_hash_table<T, __gnu_pbds::null_type, Hash, KeyEqual>; template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>> struct UnorderedSet : public pbds_unordered_set<T, Hash, KeyEqual> { UnorderedSet() : pbds_unordered_set<T, Hash, KeyEqual>() {} explicit UnorderedSet(std::size_t bucket_count, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : pbds_unordered_set<T, Hash, KeyEqual>(bucket_count, hash, equal) {} template <typename InputIt> UnorderedSet(InputIt first, InputIt last, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : pbds_unordered_set<T, Hash, KeyEqual>(first, last, bucket_count, hash, equal) {} UnorderedSet(const pbds_unordered_set<T, Hash, KeyEqual>& other) : pbds_unordered_set<T, Hash, KeyEqual>(other) {} UnorderedSet(const std::unordered_set<T, Hash, KeyEqual>& other) : pbds_unordered_set<T, Hash, KeyEqual>(other.begin(), other.end()) {} UnorderedSet(pbds_unordered_set<T, Hash, KeyEqual>&& other) : pbds_unordered_set<T, Hash, KeyEqual>(std::move(other)) {} UnorderedSet(std::initializer_list<T> init, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : pbds_unordered_set<T, Hash, KeyEqual>(init, bucket_count, hash, equal) {} typename UnorderedSet::const_iterator cbegin() const { return this->begin(); } typename UnorderedSet::const_iterator cend() const { return this->end(); } KeyEqual key_eq() const { return KeyEqual(); } std::size_t count(const T& value) const { return this->find(value) != this->end(); } template <typename... Args> std::pair<typename UnorderedSet::iterator, bool> emplace(Args&&... args) { return this->insert(T(std::forward<Args>(args)...)); } template <typename... Args> typename UnorderedSet::iterator emplace_hint(typename UnorderedSet::const_iterator hint, Args&&... args) { return this->insert(hint, T(std::forward<Args>(args)...)); } friend std::ostream& operator<<(std::ostream& os, const UnorderedSet& set) { for (auto it = set.begin(); it != set.end(); ++it) { if(it != set.begin()) os << " "; os << *it; } return os; } }; template <typename T, typename Hash = std::hash<T>, typename KeyEqual = std::equal_to<T>> struct UnorderedMultiSet : std::unordered_multiset<T, Hash, KeyEqual> { UnorderedMultiSet() : std::unordered_multiset<T, Hash, KeyEqual>() {} explicit UnorderedMultiSet(std::size_t bucket_count, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : std::unordered_multiset<T, Hash, KeyEqual>(bucket_count, hash, equal) {} template <typename InputIt> UnorderedMultiSet(InputIt first, InputIt last, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : std::unordered_multiset<T, Hash, KeyEqual>(first, last, bucket_count, hash, equal) {} UnorderedMultiSet(const std::unordered_set<T, Hash, KeyEqual>& other) : std::unordered_multiset<T, Hash, KeyEqual>(other) {} UnorderedMultiSet(std::unordered_set<T, Hash, KeyEqual>&& other) : std::unordered_multiset<T, Hash, KeyEqual>(std::move(other)) {} UnorderedMultiSet(std::initializer_list<T> init, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : std::unordered_multiset<T, Hash, KeyEqual>(init, bucket_count, hash, equal) {} friend std::ostream& operator<<(std::ostream& os, const UnorderedMultiSet& set) { for (auto it = set.begin(); it != set.end(); ++it) { if(it != set.begin()) os << " "; os << *it; } return os; } }; namespace std { template<typename T, typename Hash, typename KeyEqual> struct hash<UnorderedSet<T, Hash, KeyEqual>> { size_t operator()(const UnorderedSet<T, Hash, KeyEqual>& set) const { Vector<T> vec(set.begin(), set.end()); sort(vec.begin(), vec.end()); return hash<Vector<T>>()(vec); } }; template<typename T, typename Hash, typename KeyEqual> struct hash<UnorderedMultiSet<T, Hash, KeyEqual>> { size_t operator()(const UnorderedMultiSet<T, Hash, KeyEqual>& set) const { Vector<T> vec(set.begin(), set.end()); sort(vec.begin(), vec.end()); return hash<Vector<T>>()(vec); } }; } #line 9 "library/KowerKoint/stl-wrapper/unordered_map.hpp" template <typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>> using pbds_unordered_map = __gnu_pbds::gp_hash_table<Key, Value, Hash, KeyEqual>; template <typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>> struct UnorderedMap : public pbds_unordered_map<Key, Value, Hash, KeyEqual> { UnorderedMap() : pbds_unordered_map<Key, Value, Hash, KeyEqual>() {} explicit UnorderedMap(std::size_t bucket_count, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : pbds_unordered_map<Key, Value, Hash, KeyEqual>(bucket_count, hash, equal) {} template <typename InputIt> UnorderedMap(InputIt first, InputIt last, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : pbds_unordered_map<Key, Value, Hash, KeyEqual>(first, last, bucket_count, hash, equal) {} UnorderedMap(const pbds_unordered_map<Key, Value, Hash, KeyEqual>& other) : pbds_unordered_map<Key, Value, Hash, KeyEqual>(other) {} UnorderedMap(const std::unordered_map<Key, Value, Hash, KeyEqual>& other) : pbds_unordered_map<Key, Value, Hash, KeyEqual>(other.begin(), other.end()) {} UnorderedMap(pbds_unordered_map<Key, Value, Hash, KeyEqual>&& other) noexcept : pbds_unordered_map<Key, Value, Hash, KeyEqual>(std::move(other)) {} UnorderedMap(std::initializer_list<std::pair<Key, Value>> init, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : pbds_unordered_map<Key, Value, Hash, KeyEqual>(init, bucket_count, hash, equal) {} friend std::ostream& operator<<(std::ostream& os, const UnorderedMap& set) { for (auto it = set.begin(); it != set.end(); ++it) { os << it->first << ' ' << it->second << '\n'; } return os; } }; template <typename Key, typename Value, typename Hash = std::hash<Key>, typename KeyEqual = std::equal_to<Key>> struct UnorderedMultiMap : std::unordered_multimap<Key, Value, Hash, KeyEqual> { UnorderedMultiMap() : std::unordered_multimap<Key, Value, Hash, KeyEqual>() {} explicit UnorderedMultiMap(std::size_t bucket_count, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : std::unordered_multimap<Key, Value, Hash, KeyEqual>(bucket_count, hash, equal) {} template <typename InputIt> UnorderedMultiMap(InputIt first, InputIt last, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : std::unordered_multimap<Key, Value, Hash, KeyEqual>(first, last, bucket_count, hash, equal) {} UnorderedMultiMap(const std::unordered_map<Key, Value, Hash, KeyEqual>& other) : std::unordered_multimap<Key, Value, Hash, KeyEqual>(other) {} UnorderedMultiMap(std::unordered_map<Key, Value, Hash, KeyEqual>&& other) noexcept : std::unordered_multimap<Key, Value, Hash, KeyEqual>(std::move(other)) {} UnorderedMultiMap(std::initializer_list<std::pair<Key, Value>> init, std::size_t bucket_count = 1, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual()) : std::unordered_multimap<Key, Value, Hash, KeyEqual>(init, bucket_count, hash, equal) {} friend std::ostream& operator<<(std::ostream& os, const UnorderedMultiMap& map) { for (auto it = map.begin(); it != map.end(); ++it) { os << it->first << ' ' << it->second << '\n'; } return os; } }; namespace std { template<typename T, typename Hash, typename KeyEqual> struct hash<UnorderedMap<T, Hash, KeyEqual>> { size_t operator()(const UnorderedMap<T, Hash, KeyEqual>& map) const { Vector<T> vec(map.begin(), map.end()); sort(vec.begin(), vec.end()); return hash<Vector<T>>()(vec); } }; template<typename T, typename Hash, typename KeyEqual> struct hash<UnorderedMultiMap<T, Hash, KeyEqual>> { size_t operator()(const UnorderedMultiMap<T, Hash, KeyEqual>& map) const { Vector<T> vec(map.begin(), map.end()); sort(vec.begin(), vec.end()); return hash<Vector<T>>()(vec); } }; } #line 7 "library/KowerKoint/base.hpp" #define REP(i, n) for(int i = 0; i < (int)(n); i++) #define FOR(i, a, b) for(ll i = a; i < (ll)(b); i++) #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(),(a).rend() #define END(...) { print(__VA_ARGS__); return; } using VI = Vector<int>; using VVI = Vector<VI>; using VVVI = Vector<VVI>; using ll = long long; using VL = Vector<ll>; using VVL = Vector<VL>; using VVVL = Vector<VVL>; using ull = unsigned long long; using VUL = Vector<ull>; using VVUL = Vector<VUL>; using VVVUL = Vector<VVUL>; using VD = Vector<double>; using VVD = Vector<VD>; using VVVD = Vector<VVD>; using VS = Vector<string>; using VVS = Vector<VS>; using VVVS = Vector<VVS>; using VC = Vector<char>; using VVC = Vector<VC>; using VVVC = Vector<VVC>; using P = Pair<int, int>; using VP = Vector<P>; using VVP = Vector<VP>; using VVVP = Vector<VVP>; using LP = Pair<ll, ll>; using VLP = Vector<LP>; using VVLP = Vector<VLP>; using VVVLP = Vector<VVLP>; template <typename T> using PQ = priority_queue<T>; template <typename T> using GPQ = priority_queue<T, vector<T>, greater<T>>; constexpr int INF = 1001001001; constexpr ll LINF = 1001001001001001001ll; constexpr int DX[] = {1, 0, -1, 0}; constexpr int DY[] = {0, 1, 0, -1}; void print() { cout << '\n'; } template<typename T> void print(const T &t) { cout << t << '\n'; } template<typename Head, typename... Tail> void print(const Head &head, const Tail &... tail) { cout << head << ' '; print(tail...); } #ifdef DEBUG void dbg() { cerr << '\n'; } template<typename T> void dbg(const T &t) { cerr << t << '\n'; } template<typename Head, typename... Tail> void dbg(const Head &head, const Tail &... tail) { cerr << head << ' '; dbg(tail...); } #else template<typename... Args> void dbg(const Args &... args) {} #endif template<typename T> Vector<Vector<T>> split(typename vector<T>::const_iterator begin, typename vector<T>::const_iterator end, T val) { Vector<Vector<T>> res; Vector<T> cur; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(*it); } res.push_back(cur); return res; } Vector<string> split(typename string::const_iterator begin, typename string::const_iterator end, char val) { Vector<string> res; string cur = ""; for(auto it = begin; it != end; it++) { if(*it == val) { res.push_back(cur); cur.clear(); } else cur.push_back(*it); } res.push_back(cur); return res; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template <typename T> pair<VI, Vector<T>> compress(const vector<T> &a) { int n = a.size(); Vector<T> x; REP(i, n) x.push_back(a[i]); sort(ALL(x)); x.erase(unique(ALL(x)), x.end()); VI res(n); REP(i, n) res[i] = lower_bound(ALL(x), a[i]) - x.begin(); return make_pair(res, x); } template <typename It> auto rle(It begin, It end) { Vector<pair<typename It::value_type, int>> res; if(begin == end) return res; auto pre = *begin; int num = 1; for(auto it = begin + 1; it != end; it++) { if(pre != *it) { res.emplace_back(pre, num); pre = *it; num = 1; } else num++; } res.emplace_back(pre, num); return res; } template <typename It> Vector<pair<typename It::value_type, int>> rle_sort(It begin, It end) { Vector<typename It::value_type> cloned(begin, end); sort(ALL(cloned)); auto e = rle(ALL(cloned)); sort(ALL(e), [](const auto& l, const auto& r) { return l.second < r.second; }); return e; } template <typename T> Pair<Vector<T>, Vector<T>> factorial(int n) { Vector<T> res(n+1), rev(n+1); res[0] = 1; REP(i, n) res[i+1] = res[i] * (i+1); rev[n] = 1 / res[n]; for(int i = n; i > 0; i--) { rev[i-1] = rev[i] * i; } return make_pair(res, rev); } #line 3 "library/KowerKoint/operator.hpp" template <typename T> T add_op(T a, T b) { return a + b; } template <typename T> T sub_op(T a, T b) { return a - b; } template <typename T> T zero_e() { return T(0); } template <typename T> T div_op(T a, T b) { return a / b; } template <typename T> T mult_op(T a, T b) { return a * b; } template <typename T> T one_e() { return T(1); } template <typename T> T xor_op(T a, T b) { return a ^ b; } template <typename T> T and_op(T a, T b) { return a & b; } template <typename T> T or_op(T a, T b) { return a | b; } ll mod3() { return 998244353LL; } ll mod7() { return 1000000007LL; } ll mod9() { return 1000000009LL; } template <typename T> T max_op(T a, T b) { return max(a, b); } template <typename T> T min_op(T a, T b) { return min(a, b); } template <typename T> T max_e() { return numeric_limits<T>::max(); } template <typename T> T min_e() { return numeric_limits<T>::min(); } #line 3 "library/KowerKoint/integer/extgcd.hpp" ll extgcd(ll a, ll b, ll& x, ll& y) { x = 1, y = 0; ll nx = 0, ny = 1; while(b) { ll q = a / b; tie(a, b) = LP(b, a % b); tie(x, nx) = LP(nx, x - nx*q); tie(y, ny) = LP(ny, y - ny*q); } return a; } #line 2 "library/KowerKoint/integer/pow-mod.hpp" ll inv_mod(ll n, ll m) { n %= m; if (n < 0) n += m; ll x, y; assert(extgcd(n, m, x, y) == 1); x %= m; if(x < 0) x += m; return x; } ll pow_mod(ll a, ll n, ll m) { if(n == 0) return 1LL; if(n < 0) return inv_mod(pow_mod(a, -n, m), m); a %= m; if (a < 0) n += m; ll res = 1; while(n) { if(n & 1) { res *= a; res %= m; } n >>= 1; a *= a; a %= m; } return res; } #line 4 "library/KowerKoint/integer/modint.hpp" template <ll (*mod)()> struct Modint { ll val; Modint(): val(0) {} Modint(ll x): val(x) { val %= mod(); if(val < 0) val += mod(); } Modint& operator+=(const Modint& r) { val += r.val; if(val >= mod()) val -= mod(); return *this; } friend Modint operator+(const Modint& l, const Modint& r) { return Modint(l) += r; } Modint& operator-=(const Modint& r) { val -= r.val; if(val < 0) val += mod(); return *this; } friend Modint operator-(const Modint& l, const Modint& r) { return Modint(l) -= r; } Modint& operator*=(const Modint& r) { val *= r.val; val %= mod(); return *this; } Modint operator*(const Modint& r) { return (Modint(*this) *= r); } friend Modint operator*(const Modint& l, const Modint& r) { return Modint(l) *= r; } Modint pow(ll n) const { return Modint(pow_mod(val, n, mod())); } Modint inv() const { return Modint(inv_mod(val, mod())); } Modint& operator/=(const Modint& r) { return (*this *= r.inv()); } friend Modint operator/(const Modint& l, const Modint& r) { return Modint(l) /= r; } Modint& operator^=(const ll n) { val = pow_mod(val, n, mod()); return *this; } Modint operator^(const ll n) { return this->pow(n); } Modint operator+() const { return *this; } Modint operator-() const { return Modint() - *this; } Modint& operator++() { val++; if(val == mod()) val = 0LL; return *this; } Modint& operator++(int) { Modint res(*this); ++*this; return res; } Modint& operator--() { if(val == 0LL) val = mod(); val--; return *this; } Modint& operator--(int) { Modint res(*this); --*this; return res; } friend bool operator==(const Modint& l, const Modint& r) { return l.val == r.val; } friend bool operator!=(const Modint& l, const Modint& r) { return l.val != r.val; } static Pair<Vector<Modint>, Vector<Modint>> factorial(int n) { Vector<Modint> fact(n+1), rfact(n+1); fact[0] = 1; REP(i, n) fact[i+1] = fact[i] * (i+1); rfact[n] = 1 / fact[n]; for(int i = n-1; i >= 0; i--) rfact[i] = rfact[i+1] * (i+1); return {fact, rfact}; } friend istream& operator>>(istream& is, Modint& mi) { is >> mi.val; return is; } friend ostream& operator<<(ostream& os, const Modint& mi) { os << mi.val; return os; } }; namespace std { template<ll (*mod)()> struct hash<Modint<mod>> { size_t operator()(const Modint<mod> &p) const { return hash<ll>()(p.val); } }; } using MI3 = Modint<mod3>; using V3 = Vector<MI3>; using VV3 = Vector<V3>; using VVV3 = Vector<VV3>; using MI7 = Modint<mod7>; using V7 = Vector<MI7>; using VV7 = Vector<V7>; using VVV7 = Vector<VV7>; using MI9 = Modint<mod9>; using V9 = Vector<MI9>; using VV9 = Vector<V9>; using VVV9 = Vector<VV9>; #line 3 "library/KowerKoint/counting/counting.hpp" template <typename T> struct Counting { Vector<T> fact, ifact; Counting() {} Counting(ll n) { assert(n >= 0); expand(n); } void expand(ll n) { assert(n >= 0); ll sz = (ll)fact.size(); if(sz > n) return; fact.resize(n+1); ifact.resize(n+1); fact[0] = 1; FOR(i, max(1LL, sz), n+1) fact[i] = fact[i-1] * i; ifact[n] = 1 / fact[n]; for(ll i = n-1; i >= sz; i--) ifact[i] = ifact[i+1] * (i+1); } T p(ll n, ll r) { if(n < r) return 0; assert(r >= 0); expand(n); return fact[n] * ifact[n-r]; } T c(ll n, ll r) { if(n < r) return 0; assert(r >= 0); expand(n); return fact[n] * ifact[r] * ifact[n-r]; } T h(ll n, ll r) { assert(n >= 0); assert(r >= 0); return c(n+r-1, r); } T stirling(ll n, ll k) { if(n < k) return 0; assert(k >= 0); if(n == 0) return 1; T res = 0; int sign = k%2? -1 : 1; expand(k); REP(i, k+1) { res += sign * ifact[i] * ifact[k-i] * T(i).pow(n); sign *= -1; } return res; } Vector<Vector<T>> stirling_table(ll n, ll k) { assert(n >= 0 && k >= 0); Vector<Vector<T>> res(n+1, Vector<T>(k+1)); res[0][0] = 1; FOR(i, 1, n+1) FOR(j, 1, k+1) { res[i][j] = res[i-1][j-1] + j * res[i-1][j]; } return res; } T bell(ll n, ll k) { assert(n >= 0 && k >= 0); expand(k); Vector<T> tmp(k+1); int sign = 1; tmp[0] = 1; FOR(i, 1, k+1) { sign *= -1; tmp[i] = tmp[i-1] + sign * ifact[i]; } T res = 0; REP(i, k+1) { res += T(i).pow(n) * ifact[i] * tmp[k-i]; } return res; } Vector<Vector<T>> partition_table(ll n, ll k) { assert(n >= 0 && k >= 0); Vector<Vector<T>> res(n+1, Vector<T>(k+1)); REP(i, k+1) res[0][i] = 1; FOR(i, 1, n+1) FOR(j, 1, k+1) { res[i][j] = res[i][j-1] + (i<j? 0 : res[i-j][j]); } return res; } }; #line 2 "Contests/main.cpp" /* #include <atcoder/all> */ /* using namespace atcoder; */ /* #include "KowerKoint/expansion/ac-library/all.hpp" */ void solve(){ int n, m, l; cin >> n >> m >> l; VI a(n); cin >> a; array<int, 1001> dp = {}; dp[l] = 1; REP(i, n) { array<int, 1001> ndp = dp; REP(j, 1001) ndp[(j+a[i])/2] |= dp[j]; swap(dp, ndp); } print(dp[m]? "Yes" : "No"); } // generated by oj-template v4.7.2 (https://github.com/online-judge-tools/template-generator) int main() { // Fasterize input/output script ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(100); // scanf/printf user should delete this fasterize input/output script int t = 1; //cin >> t; // comment out if solving multi testcase for(int testCase = 1;testCase <= t;++testCase){ solve(); } return 0; }