#1175112 (C++23(gcc16)) No.3670 Fast Knapsack

• 問題: No.3670 Fast Knapsack
• ユーザー: harurun
• 提出日時: 2026-08-06 04:39:52
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 1,070 ms / 2,500 ms
• コード長: 14,749 bytes
• コンパイル時間: 2,518 ms
• コンパイル使用メモリ: 355,400 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-09-04 22:07:28
• 合計ジャッジ時間: 17,710 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 25

ソースコード

#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll=long long;

template<std::size_t length> struct Bitset {
private:
    using word_type = std::uint64_t;
    static constexpr std::size_t word_bits = 64;
    static constexpr std::size_t word_count = (length + word_bits - 1) / word_bits;
    std::array<word_type, word_count> arr{};
    static constexpr word_type lower_mask(std::size_t bits) noexcept {
        if (bits == 0) return word_type{0};
        if (bits >= word_bits) return ~word_type{0};
        return (word_type{1} << bits) - 1;
    }
    static constexpr word_type last_word_mask() noexcept {
        if constexpr (length == 0) {
            return word_type{0};
        } else if constexpr (length % word_bits == 0) {
            return ~word_type{0};
        } else {
            return lower_mask(length % word_bits);
        }
    }
    constexpr void trim() noexcept {
        if constexpr (word_count != 0) {
            arr.back() &= last_word_mask();
        }
    }
    static constexpr void check_position(std::size_t pos) {
        if (pos >= length) {
            throw std::out_of_range("Bitset position is out of range");
        }
    }
    constexpr bool test_unchecked(std::size_t pos) const noexcept {
        return ((arr[pos / word_bits] >> (pos % word_bits)) & word_type{1}) != 0;
    }
    constexpr void set_unchecked(std::size_t pos, bool value) noexcept {
        const std::size_t x = pos / word_bits;
        const word_type mask = word_type{1} << (pos % word_bits);
        if (value) {
            arr[x] |= mask;
        } else {
            arr[x] &= ~mask;
        }
    }
    template<class CharT, class Traits> constexpr void assign_from_string( std::basic_string_view<CharT, Traits> str, std::size_t pos, std::size_t count, CharT zero, CharT one ) {
        if (pos > str.size()) {
            throw std::out_of_range("Bitset string position is out of range");
        }
        reset();
        const std::size_t rlen = std::min(count, str.size() - pos);
        for (std::size_t i = 0; i < rlen; ++i) {
            const CharT c = str[pos + i];
            if (!Traits::eq(c, zero) && !Traits::eq(c, one)) {
                throw std::invalid_argument("Bitset string contains a non-binary character");
            }
        }
        const std::size_t used = std::min(length, rlen);
        for (std::size_t i = 0; i < used; ++i) {
            const CharT c = str[pos + used - 1 - i];
            if (Traits::eq(c, one)) {
                set_unchecked(i, true);
            }
        }
    }
    template<class UInt> constexpr UInt to_unsigned_integer(const char* message) const {
        static_assert(std::is_unsigned_v<UInt>);
        constexpr std::size_t digits = std::numeric_limits<UInt>::digits;
        for (std::size_t i = digits; i < length; ++i) {
            if (test_unchecked(i)) {
                throw std::overflow_error(message);
            }
        }
        UInt result = 0;
        const std::size_t used = std::min(length, digits);
        for (std::size_t i = 0; i < used; ++i) {
            if (test_unchecked(i)) {
                result |= (UInt{1} << i);
            }
        }
        return result;
    }
public:
    class reference {
        friend struct Bitset;
    private:
        Bitset* owner;
        std::size_t pos;
        constexpr reference(Bitset& owner_, std::size_t pos_) noexcept : owner(&owner_), pos(pos_) {}
    public:
        constexpr reference(const reference&) noexcept = default;
        constexpr ~reference() noexcept = default;
        constexpr reference& operator=(bool value) noexcept {
            owner->set_unchecked(pos, value);
            return *this;
        }
        constexpr reference& operator=(const reference& rhs) noexcept {
            return *this = static_cast<bool>(rhs);
        }
        constexpr const reference& operator=(bool value) const noexcept {
            owner->set_unchecked(pos, value);
            return *this;
        }
        constexpr bool operator~() const noexcept {
            return !owner->test_unchecked(pos);
        }
        constexpr operator bool() const noexcept {
            return owner->test_unchecked(pos);
        }
        constexpr reference& flip() noexcept {
            owner->arr[pos / word_bits] ^= word_type{1} << (pos % word_bits);
            return *this;
        }
        friend constexpr void swap(reference lhs, reference rhs) noexcept {
            const bool temp = static_cast<bool>(lhs);
            lhs = static_cast<bool>(rhs);
            rhs = temp;
        }
        friend constexpr void swap(reference lhs, bool& rhs) noexcept {
            const bool temp = static_cast<bool>(lhs);
            lhs = rhs;
            rhs = temp;
        }
        friend constexpr void swap(bool& lhs, reference rhs) noexcept {
            swap(rhs, lhs);
        }
    };
    constexpr Bitset() noexcept = default;
    constexpr Bitset(const Bitset&) noexcept = default;
    constexpr Bitset& operator=(const Bitset&) noexcept = default;
    constexpr ~Bitset() noexcept = default;
    constexpr Bitset(unsigned long long value) noexcept {
        if constexpr (word_count != 0) {
            arr[0] = static_cast<word_type>(value);
            trim();
        }
    }
    template<class CharT, class Traits, class Allocator> explicit constexpr Bitset( const std::basic_string<CharT, Traits, Allocator>& str, typename std::basic_string<CharT, Traits, Allocator>::size_type pos = 0, typename std::basic_string<CharT, Traits, Allocator>::size_type count = std::basic_string<CharT, Traits, Allocator>::npos, CharT zero = CharT('0'), CharT one = CharT('1') ) {
        assign_from_string( std::basic_string_view<CharT, Traits>(str.data(), str.size()), pos, count, zero, one );
    }
    template<class CharT, class Traits> explicit constexpr Bitset( std::basic_string_view<CharT, Traits> str, typename std::basic_string_view<CharT, Traits>::size_type pos = 0, typename std::basic_string_view<CharT, Traits>::size_type count = std::basic_string_view<CharT, Traits>::npos, CharT zero = CharT('0'), CharT one = CharT('1') ) {
        assign_from_string(str, pos, count, zero, one);
    }
    template<class CharT> explicit constexpr Bitset( const CharT* str, typename std::basic_string_view<CharT>::size_type count = std::basic_string_view<CharT>::npos, CharT zero = CharT('0'), CharT one = CharT('1') ) : Bitset( count == std::basic_string_view<CharT>::npos ? std::basic_string_view<CharT>(str) : std::basic_string_view<CharT>(str, count), 0, count, zero, one ) {}
    constexpr Bitset& operator&=(const Bitset& rhs) noexcept {
        for (std::size_t i = 0; i < word_count; ++i) {
            arr[i] &= rhs.arr[i];
        }
        return *this;
    }
    constexpr Bitset& operator|=(const Bitset& rhs) noexcept {
        for (std::size_t i = 0; i < word_count; ++i) {
            arr[i] |= rhs.arr[i];
        }
        return *this;
    }
    constexpr Bitset& operator^=(const Bitset& rhs) noexcept {
        for (std::size_t i = 0; i < word_count; ++i) {
            arr[i] ^= rhs.arr[i];
        }
        return *this;
    }
    constexpr Bitset& operator<<=(std::size_t shift) noexcept {
        if (shift >= length) {
            return reset();
        }
        if (shift == 0) {
            return *this;
        }
        const std::size_t whole_words = shift / word_bits;
        const std::size_t inner_shift = shift % word_bits;
        for (std::size_t i = word_count; i-- > 0;) {
            word_type value = 0;
            if (i >= whole_words) {
                value = arr[i - whole_words] << inner_shift;
                if (inner_shift != 0 && i > whole_words) {
                    value |= arr[i - whole_words - 1] >> (word_bits - inner_shift);
                }
            }
            arr[i] = value;
        }
        trim();
        return *this;
    }
    constexpr Bitset& operator>>=(std::size_t shift) noexcept {
        if (shift >= length) {
            return reset();
        }
        if (shift == 0) {
            return *this;
        }
        const std::size_t whole_words = shift / word_bits;
        const std::size_t inner_shift = shift % word_bits;
        for (std::size_t i = 0; i < word_count; ++i) {
            const std::size_t source = i + whole_words;
            word_type value = 0;
            if (source < word_count) {
                value = arr[source] >> inner_shift;
                if (inner_shift != 0 && source + 1 < word_count) {
                    value |= arr[source + 1] << (word_bits - inner_shift);
                }
            }
            arr[i] = value;
        }
        return *this;
    }
    constexpr Bitset operator<<(std::size_t shift) const noexcept {
        Bitset result(*this);
        result <<= shift;
        return result;
    }
    constexpr Bitset operator>>(std::size_t shift) const noexcept {
        Bitset result(*this);
        result >>= shift;
        return result;
    }
    constexpr Bitset& set() noexcept {
        arr.fill(~word_type{0});
        trim();
        return *this;
    }
    constexpr Bitset& set(std::size_t pos, bool value = true) {
        check_position(pos);
        set_unchecked(pos, value);
        return *this;
    }
    constexpr Bitset& reset() noexcept {
        arr.fill(word_type{0});
        return *this;
    }
    constexpr Bitset& reset(std::size_t pos) {
        check_position(pos);
        set_unchecked(pos, false);
        return *this;
    }
    constexpr Bitset operator~() const noexcept {
        Bitset result(*this);
        result.flip();
        return result;
    }
    constexpr Bitset& flip() noexcept {
        for (word_type& value : arr) {
            value = ~value;
        }
        trim();
        return *this;
    }
    constexpr Bitset& flip(std::size_t pos) {
        check_position(pos);
        arr[pos / word_bits] ^= word_type{1} << (pos % word_bits);
        return *this;
    }
    constexpr bool operator[](std::size_t pos) const noexcept {
        assert(pos < length);
        return test_unchecked(pos);
    }
    constexpr reference operator[](std::size_t pos) noexcept {
        assert(pos < length);
        return reference(*this, pos);
    }
    constexpr unsigned long to_ulong() const {
        return to_unsigned_integer<unsigned long>("Bitset does not fit in unsigned long");
    }
    constexpr unsigned long long to_ullong() const {
        return to_unsigned_integer<unsigned long long>( "Bitset does not fit in unsigned long long" );
    }
    template< class CharT = char, class Traits = std::char_traits<CharT>, class Allocator = std::allocator<CharT> > constexpr std::basic_string<CharT, Traits, Allocator> to_string( CharT zero = CharT('0'), CharT one = CharT('1') ) const {
        std::basic_string<CharT, Traits, Allocator> result(length, zero);
        for (std::size_t i = 0; i < length; ++i) {
            if (test_unchecked(i)) {
                result[length - 1 - i] = one;
            }
        }
        return result;
    }
    constexpr std::size_t count() const noexcept {
        std::size_t result = 0;
        for (word_type value : arr) {
            result += static_cast<std::size_t>(std::popcount(value));
        }
        return result;
    }
    constexpr std::size_t size() const noexcept {
        return length;
    }
    constexpr bool operator==(const Bitset& rhs) const noexcept {
        return arr == rhs.arr;
    }
    constexpr bool operator!=(const Bitset& rhs) const noexcept {
        return !(*this == rhs);
    }
    constexpr bool test(std::size_t pos) const {
        check_position(pos);
        return test_unchecked(pos);
    }
    constexpr bool get(std::size_t pos) const {
        return test(pos);
    }
    constexpr bool all() const noexcept {
        return count() == length;
    }
    constexpr bool any() const noexcept {
        for (word_type value : arr) {
            if (value != 0) {
                return true;
            }
        }
        return false;
    }
    constexpr bool none() const noexcept {
        return !any();
    }
    constexpr std::size_t bit_length() const noexcept {
        for (std::size_t i = word_count; i-- > 0;) {
            if (arr[i] != 0) {
                return i * word_bits + std::bit_width(arr[i]);
            }
        }
        return 0;
    }
};
template<std::size_t length> constexpr Bitset<length> operator&( Bitset<length> lhs, const Bitset<length>& rhs ) noexcept {
    lhs &= rhs;
    return lhs;
}
template<std::size_t length> constexpr Bitset<length> operator|( Bitset<length> lhs, const Bitset<length>& rhs ) noexcept {
    lhs |= rhs;
    return lhs;
}
template<std::size_t length> constexpr Bitset<length> operator^( Bitset<length> lhs, const Bitset<length>& rhs ) noexcept {
    lhs ^= rhs;
    return lhs;
}
template<class CharT, class Traits, std::size_t length> std::basic_ostream<CharT, Traits>& operator<<( std::basic_ostream<CharT, Traits>& os, const Bitset<length>& value ) {
    return os << value.template to_string<CharT, Traits>( os.widen('0'), os.widen('1') );
}
template<class CharT, class Traits, std::size_t length> std::basic_istream<CharT, Traits>& operator>>( std::basic_istream<CharT, Traits>& is, Bitset<length>& value ) {
    typename std::basic_istream<CharT, Traits>::sentry sentry(is);
    if (!sentry) {
        return is;
    }
    std::basic_string<CharT, Traits> str;
    str.reserve(length);
    const CharT zero = is.widen('0');
    const CharT one = is.widen('1');
    auto* buffer = is.rdbuf();
    std::ios_base::iostate state = std::ios_base::goodbit;
    while (str.size() < length) {
        const typename Traits::int_type next = buffer->sgetc();
        if (Traits::eq_int_type(next, Traits::eof())) {
            state |= std::ios_base::eofbit;
            break;
        }
        const CharT c = Traits::to_char_type(next);
        if (!Traits::eq(c, zero) && !Traits::eq(c, one)) {
            break;
        }
        str.push_back(c);
        buffer->snextc();
    }
    if constexpr (length > 0) {
        if (str.empty()) {
            state |= std::ios_base::failbit;
        } else {
            value = Bitset<length>(str, 0, str.size(), zero, one);
        }
    }
    if (state != std::ios_base::goodbit) {
        is.setstate(state);
    }
    return is;
}



Bitset<200001> C;
Bitset<200001> mask;

void solve(){
    ll N,S;
    cin>>N>>S;
    C.reset();
    mask.reset();
    mask.flip();
    mask<<=(S+1);
    mask.flip();
    vector<ll> A(N);
    for(ll i=0;i<N;i++){
        cin>>A[i];
    }
    C.set(0);
    for(ll i:A){
        C|=C<<i;
    }
    C&=mask;
    cout<<C.bit_length()-1<<"\n";
}

int main(){
    ll T;
    cin>>T;
    while(T--){
        solve();
    }
}