結果

問題 No.1538 引きこもりさんは引き算が得意。
コンテスト
ユーザー LyricalMaestro
提出日時 2026-07-20 00:57:27
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 153 ms / 2,000 ms
+ 96µs
コード長 2,080 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 224 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 125,736 KB
最終ジャッジ日時 2026-07-20 00:57:36
合計ジャッジ時間 7,108 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 54
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

## https://yukicoder.me/problems/no/1538


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for a in A:
        if a == K:
            print("Yes")
            return

    N1 = N // 2
    N2 = N - N1
    array1 = []
    for bit in range(3 ** N1):
        b = bit
        p_count = 0
        m_count = 0
        ans = 0
        for i in range(N1):
            a = b % 3
            if a == 1:
                ans += A[i]
                p_count += 1
            elif a == 2:
                ans -= A[i]
                m_count += 1
            b //= 3
        array1.append((p_count, m_count, ans))
        
    array2 = []
    for bit in range(3 ** N2):
        b = bit
        p_count = 0
        m_count = 0
        ans = 0
        for i in range(N2):
            a = b % 3
            if a == 1:
                ans += A[N1 + i]
                p_count += 1
            elif a == 2:
                ans -= A[N1 + i]
                m_count += 1
            b //= 3
        array2.append((p_count, m_count, ans))

    # p > 0 and m > 0 用
    map1 = set()
    for _, _, ans in array2:
        map1.add(ans)
    # p > 0 and m == 0 用
    map2 = set()
    for _, m, ans in array2:
        if m > 0:
            map2.add(ans)
    # p == 0 and m > 0 用
    map3 = set()
    for p, _, ans in array2:
        if p > 0:
            map3.add(ans)
    # p == 0 and m == 0用
    map4 = set()
    for p, m, ans in array2:
        if p > 0 and m > 0:
            map4.add(ans)

    for p, m, ans in array1:
        if p > 0 and m > 0:
            if (K - ans) in map1:
                print("Yes")
                return
        elif p > 0 and m == 0:
            if (K - ans) in map2:
                print("Yes")
                return
        elif p == 0 and m > 0:
            if (K - ans) in map3:
                print("Yes")
                return
        elif p == 0 and m == 0:
            if (K - ans) in map4:
                print("Yes")
                return
    print("No")


        




if __name__ == "__main__":
    main()
0