結果

問題 No.332 数列をプレゼントに
ユーザー gew1fw
提出日時 2025-06-12 19:32:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,448 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 438,952 KB
最終ジャッジ日時 2025-06-12 19:32:22
合計ジャッジ時間 8,765 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 17 TLE * 1 MLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, X = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    sum_A = sum(A)
    if sum_A < X:
        print("No")
        return

    if N <= 40:
        mid = N // 2
        A1 = A[:mid]
        A2 = A[mid:]

        # Generate all subsets for A1
        subsets_A1 = []
        for mask in range(0, 1 << mid):
            s = 0
            indices = []
            for i in range(mid):
                if mask & (1 << i):
                    s += A1[i]
                    indices.append(i)  # relative indices in A1
            subsets_A1.append((s, indices))

        # Generate all subsets for A2, including their original indices
        a2_dict = {}
        for mask in range(0, 1 << (N - mid)):
            s = 0
            indices = []
            for i in range(len(A2)):
                if mask & (1 << i):
                    s += A2[i]
                    indices.append(mid + i)  # original index
            if s not in a2_dict:
                a2_dict[s] = []
            a2_dict[s].append(indices)

        # Check all possible combinations
        found = False
        for s_a, indices_a in subsets_A1:
            required = X - s_a
            if required < 0:
                continue
            if required in a2_dict:
                for indices_b in a2_dict[required]:
                    combined = set(indices_a + indices_b)
                    res = ['x'] * N
                    for i in combined:
                        res[i] = 'o'
                    print(''.join(res))
                    found = True
                    return
        if not found:
            print("No")
    else:
        prev = {0: None}
        for i in range(N):
            a = A[i]
            current_sums = list(prev.keys())
            for s in current_sums:
                new_s = s + a
                if new_s > X:
                    continue
                if new_s not in prev:
                    prev[new_s] = (i, s)
        if X not in prev:
            print("No")
        else:
            current_sum = X
            indices = set()
            while current_sum != 0:
                idx, prev_sum = prev[current_sum]
                indices.add(idx)
                current_sum = prev_sum
            res = ['x'] * N
            for i in indices:
                res[i] = 'o'
            print(''.join(res))

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