結果

問題 No.332 数列をプレゼントに
ユーザー qwewe
提出日時 2025-04-24 12:20:42
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,850 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 338,340 KB
最終ジャッジ日時 2025-04-24 12:21:01
合計ジャッジ時間 4,543 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 1 MLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def generate_subset_sums(arr, max_sum):
    n = len(arr)
    sums = defaultdict(list)
    def backtrack(index, current_sum, mask):
        if index == n:
            sums[current_sum].append(mask)
            return
        # Include the current element
        new_sum = current_sum + arr[index]
        if new_sum <= max_sum:
            backtrack(index + 1, new_sum, mask | (1 << index))
        # Exclude the current element
        backtrack(index + 1, current_sum, mask)
    backtrack(0, 0, 0)
    return sums

def main():
    N, X = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    
    B = []
    B_indices = []
    for i in range(N):
        if A[i] <= X:
            B.append(A[i])
            B_indices.append(i)
    
    sum_B = sum(B)
    if sum_B < X:
        print("No")
        return
    if sum_B == X:
        s = ['x'] * N
        for idx in B_indices:
            s[idx] = 'o'
        print(''.join(s))
        return
    
    diff = sum_B - X
    m = len(B)
    k = m // 2
    first = B[:k]
    second = B[k:]
    
    first_sums = generate_subset_sums(first, diff)
    second_sums = generate_subset_sums(second, diff)
    
    found = False
    mask_left = 0
    mask_right = 0
    for sum_left in first_sums:
        sum_right = diff - sum_left
        if sum_right in second_sums:
            mask_left = first_sums[sum_left][0]
            mask_right = second_sums[sum_right][0]
            found = True
            break
    
    if not found:
        print("No")
    else:
        total_mask = mask_left | (mask_right << len(first))
        s = ['x'] * N
        for j in range(m):
            if not (total_mask & (1 << j)):
                s[B_indices[j]] = 'o'
        print(''.join(s))

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