結果

問題 No.332 数列をプレゼントに
ユーザー qwewe
提出日時 2025-05-14 12:47:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,683 bytes
コンパイル時間 289 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 115,856 KB
最終ジャッジ日時 2025-05-14 12:49:03
合計ジャッジ時間 4,736 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 36 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, x = map(int, input().split())
a = list(map(int, input().split()))

# Filter out elements greater than x and collect their original indices
rest_a = []
original_indices = []
for idx, num in enumerate(a):
    if num <= x:
        rest_a.append(num)
        original_indices.append(idx)

sum_rest = sum(rest_a)

if sum_rest < x:
    print("No")
elif sum_rest == x:
    # All elements in rest_a are used, others are excluded
    res = ['o' if idx in original_indices else 'x' for idx in range(n)]
    print(''.join(res))
else:
    K = sum_rest - x
    if K == 0:
        res = ['o' if idx in original_indices else 'x' for idx in range(n)]
        print(''.join(res))
    else:
        # Check if K can be formed by a subset of rest_a
        # For large K, check if any single element equals K
        if K > 1e6:
            found = False
            for i in range(len(rest_a)):
                if rest_a[i] == K:
                    # Construct the answer
                    res = ['x'] * n
                    # Mark all elements not in rest_a as 'x'
                    for idx in range(n):
                        if a[idx] > x:
                            res[idx] = 'x'
                        else:
                            if idx == original_indices[i]:
                                res[idx] = 'x'
                            else:
                                res[idx] = 'o'
                    print(''.join(res))
                    found = True
                    break
            if not found:
                print("No")
        else:
            # Use dynamic programming
            max_k = K
            dp = [False] * (max_k + 1)
            prev = [[] for _ in range(max_k + 1)]
            dp[0] = True
            prev[0] = []
            for i in range(len(rest_a)):
                num = rest_a[i]
                for j in range(max_k, num - 1, -1):
                    if dp[j - num] and not dp[j]:
                        dp[j] = True
                        prev[j] = prev[j - num] + [i]
            if dp[K]:
                selected = prev[K]
                # Build the result
                selected_in_original = set()
                for i in selected:
                    selected_in_original.add(original_indices[i])
                res = []
                for idx in range(n):
                    if a[idx] > x:
                        res.append('x')
                    else:
                        if idx in selected_in_original:
                            res.append('x')
                        else:
                            res.append('o')
                print(''.join(res))
            else:
                print("No")
0