結果

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

ソースコード

diff # 

def solve():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, K_val = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    queries = []
    for _ in range(Q):
        x, v = int(input[ptr]), int(input[ptr+1])
        queries.append((x-1, v))
        ptr += 2
    
    for x, v in queries:
        A[x] = v
        B = []
        sum_B = 0
        for a in A:
            if a <= K_val:
                B.append(a)
                sum_B += a
        if sum_B < K_val:
            print(0)
            continue
        if K_val == 0:
            print(1)
            continue
        B.sort(reverse=True)
        dp = [False] * (K_val + 1)
        dp[0] = True
        found = False
        for a in B:
            if a == 0:
                continue
            for i in range(K_val, a - 1, -1):
                if dp[i - a]:
                    if not dp[i]:
                        dp[i] = True
                        if i == K_val:
                            found = True
                            break
            if found:
                break
        print(1 if found else 0)

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