結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    X = int(input[ptr])
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N

    # Sort the array in descending order along with original indices
    sorted_list = sorted([(A[i], i) for i in range(N)], key=lambda x: (-x[0], x[1]))
    sorted_A = [x[0] for x in sorted_list]
    original_indices = [x[1] for x in sorted_list]

    # Compute prefix sums
    prefix_sum = [0] * (N + 1)
    for i in range(N):
        prefix_sum[i+1] = prefix_sum[i] + sorted_A[i]

    stack = []
    stack.append( (0, 0, 0) )
    found = False

    while stack:
        i, s, mask = stack.pop()
        if s == X:
            # Reconstruct the result
            selected = [False] * N
            for bit in range(N):
                if mask & (1 << bit):
                    original_idx = original_indices[bit]
                    selected[original_idx] = True
            # Create the output string
            output = ['x'] * N
            for j in range(N):
                if selected[j]:
                    output[j] = 'o'
            print(''.join(output))
            found = True
            break
        if s > X:
            continue
        if i < N:
            remaining_sum = prefix_sum[N] - prefix_sum[i]
            if s + remaining_sum < X:
                continue
            # Try including the current element
            new_s = s + sorted_A[i]
            if new_s <= X:
                new_mask = mask | (1 << i)
                stack.append( (i+1, new_s, new_mask) )
            # Try excluding the current element
            stack.append( (i+1, s, mask) )

    if not found:
        print("No")

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