結果

問題 No.868 ハイパー部分和問題
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:49:29
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,044 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 59,284 KB
最終ジャッジ日時 2025-06-12 20:51:18
合計ジャッジ時間 9,891 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 14 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0

    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1

    A = list(map(int, input[ptr:ptr+N]))
    ptr += N

    Q = int(input[ptr])
    ptr += 1

    queries = []
    for _ in range(Q):
        x = int(input[ptr]) - 1  # 0-based index
        ptr += 1
        v = int(input[ptr])
        ptr += 1
        queries.append((x, v))

    results = []

    for x, v in queries:
        A[x] = v

        # Compute subset sum up to K
        max_sum = K
        dp = [False] * (max_sum + 1)
        dp[0] = True

        for a in A:
            if a == 0:
                continue
            if a > max_sum:
                continue
            # Iterate in reverse to avoid reusing the same element multiple times
            for s in range(max_sum, a - 1, -1):
                if dp[s - a]:
                    dp[s] = True

        results.append(1 if dp[K] else 0)

    for res in results:
        print(res)

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