結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー 高橋ゆに
提出日時 2025-08-08 11:51:37
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,103 bytes
コンパイル時間 1,358 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 848,080 KB
最終ジャッジ日時 2025-09-09 17:09:41
合計ジャッジ時間 6,693 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 73
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    N, W = map(int, input().split())
    VALUES = list(map(int, input().split()))
    WEIGHTS = list(map(int, input().split()))
    
    scores = [[-1] * (W + 1) for _ in range(N + 1)]
    paths = [[[] for _ in range(W + 1)] for _ in range(N + 1)]
    
    scores[0][0] = 0
    for i in range(N):
        v = VALUES[i]
        added_w = WEIGHTS[i]
        
        for w in range(W + 1):
            if scores[i][w] != -1:
                scores[i + 1][w] =  scores[i][w]
                paths[i + 1][w] = paths[i][w]
        
        for w in range(W + 1):
            new_w = w + added_w
            new_score = scores[i][w] + v
            if new_w <= W and scores[i + 1][new_w] <= new_score and paths[i + 1][new_w] < paths[i][w] + [i + 1]:
                scores[i + 1][new_w] = new_score
                paths[i + 1][new_w] = paths[i][w] + [i + 1]
    
    path = []  
    for w in reversed(range(W + 1)):
        if scores[-1][w] != -1:
            path = paths[-1][w]
            break
    
    print(len(path))
    print(*path)
                
if __name__ == "__main__":
    main()
0