結果

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

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1000000)
    n, x = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    # 预处理：排除所有大于x的元素，并记录它们的索引
    elements = [(a[i], i) for i in range(n) if a[i] <= x]
    m = len(elements)
    if m == 0:
        print("No")
        return
    
    sum_total = sum(num for num, idx in elements)
    if sum_total < x:
        print("No")
        return
    
    # 按降序排列
    elements.sort(reverse=True, key=lambda x: x[0])
    
    # 计算后缀和
    suffix_sum = [0] * (m + 1)
    for i in range(m-1, -1, -1):
        suffix_sum[i] = suffix_sum[i+1] + elements[i][0]
    
    selected = [False] * n
    
    # 回溯函数
    def backtrack(pos, current_sum, path):
        if current_sum == x:
            for idx in path:
                selected[elements[idx][1]] = True
            return True
        if pos >= m:
            return False
        
        # 不选当前元素
        if backtrack(pos + 1, current_sum, path):
            return True
        
        # 选当前元素，如果当前sum + 元素的值 <=x 并且加上后缀和可能达到x
        if current_sum + elements[pos][0] > x:
            return False
        if current_sum + elements[pos][0] + suffix_sum[pos+1] < x:
            return False  # 剪枝
        
        if backtrack(pos + 1, current_sum + elements[pos][0], path + [pos]):
            return True
        return False
    
    found = backtrack(0, 0, [])
    if found:
        s = ''.join('o' if selected[i] else 'x' for i in range(n))
        print(s)
    else:
        print("No")

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