結果

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

ソースコード

diff # 

import sys
sys.setrecursionlimit(1000000)

def main():
    import sys
    n, x = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    
    total = sum(a)
    if total < x:
        print("No")
        return
    
    a.sort(reverse=True)
    suffix_sum = [0] * (n + 1)
    for i in range(n-1, -1, -1):
        suffix_sum[i] = suffix_sum[i+1] + a[i]
    
    result = [False] * n
    
    found = False
    path = []
    
    def backtrack(index, current_sum):
        nonlocal found
        if found:
            return
        if current_sum == x:
            for i in range(index, n):
                result[i] = False
            for idx in path:
                result[idx] = True
            found = True
            return
        if current_sum > x or index == n:
            return
        
        # 不选当前元素
        backtrack(index + 1, current_sum)
        if found:
            return
        
        # 选当前元素
        new_sum = current_sum + a[index]
        if new_sum > x:
            return
        
        remaining = suffix_sum[index + 1]
        if new_sum + remaining < x:
            return
        
        path.append(index)
        backtrack(index + 1, new_sum)
        path.pop()
    
    backtrack(0, 0)
    
    if not found:
        print("No")
    else:
        s = []
        for i in range(n):
            if result[i]:
                s.append('o')
            else:
                s.append('x')
        print(''.join(s))

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