結果

問題 No.332 数列をプレゼントに
ユーザー qwewe
提出日時 2025-04-24 12:21:04
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,016 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 844,340 KB
最終ジャッジ日時 2025-04-24 12:23:04
合計ジャッジ時間 5,318 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 11 MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    X = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    
    # Step 1: Exclude elements greater than X
    B = []
    exclude_indices = []
    for i in range(N):
        if A[i] <= X:
            B.append((A[i], i))
        else:
            exclude_indices.append(i)
    
    # Step 2: Check sum of B
    sum_B = sum(a for a, _ in B)
    if sum_B < X:
        print("No")
        return
    
    T = sum_B - X
    if T == 0:
        # All elements in B are selected
        res = ['o' if i not in exclude_indices else 'x' for i in range(N)]
        print(''.join(res))
        return
    
    # Step 3: Check if any single element equals T
    for a, i in B:
        if a == T:
            res = ['x'] * N
            for _, idx_in_B in B:
                res[idx_in_B] = 'o' if idx_in_B != i else 'x'
            for idx_excl in exclude_indices:
                res[idx_excl] = 'x'
            print(''.join(res))
            return
    
    # Step 4: Use dynamic programming to find subset sum T
    elements = [a for a, _ in B]
    n = len(elements)
    max_T = T
    dp = [False] * (max_T + 1)
    dp[0] = True
    last = [None] * (max_T + 1)
    
    for i in range(n):
        a = elements[i]
        for j in range(max_T, a-1, -1):
            if dp[j - a] and not dp[j]:
                dp[j] = True
                last[j] = i
    
    if not dp[T]:
        print("No")
        return
    
    # Reconstruct the subset
    subset = set()
    current = T
    while current > 0:
        i = last[current]
        subset.add(i)
        current -= elements[i]
    
    # Build the result
    res = ['x'] * N
    for i in range(len(B)):
        a, original_idx = B[i]
        if i not in subset:
            res[original_idx] = 'o'
    for idx_excl in exclude_indices:
        res[idx_excl] = 'x'
    print(''.join(res))

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