結果

問題 No.332 数列をプレゼントに
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:34:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,329 bytes
コンパイル時間 515 ms
コンパイル使用メモリ 82,108 KB
実行使用メモリ 96,036 KB
最終ジャッジ日時 2025-06-12 19:34:59
合計ジャッジ時間 5,491 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 16 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, X = map(int, input().split())
A = list(map(int, input().split()))

# 创建包含值和原索引的列表，并按值从大到小排序
elements = []
for i in range(n):
    elements.append((A[i], i))
elements.sort(reverse=True, key=lambda x: x[0])

# 预计算从每个位置i到末尾的元素总和
sum_remain = [0] * (n + 1)
for i in range(n-1, -1, -1):
    sum_remain[i] = sum_remain[i+1] + elements[i][0]

selected = []
found = False

def backtrack(i, current_sum):
    global found
    if found:
        return
    if current_sum == X:
        found = True
        return
    if current_sum > X or i >= n:
        return
    # 剪枝条件：剩下的元素总和不足以达到目标
    if current_sum + sum_remain[i] < X:
        return
    # 尝试不选当前元素
    backtrack(i+1, current_sum)
    if found:
        return
    # 尝试选中当前元素
    new_sum = current_sum + elements[i][0]
    if new_sum > X:
        return
    # 剪枝条件：剩下的元素总和不足以达到目标
    if new_sum + sum_remain[i+1] < X:
        return
    selected.append(elements[i][1])
    backtrack(i+1, new_sum)
    if found:
        return
    selected.pop()

backtrack(0, 0)

if found:
    result = ['x'] * n
    for idx in selected:
        result[idx] = 'o'
    print(''.join(result))
else:
    print("No")
0