結果

問題 No.3329 Only the Rightest Choice is Right!!!
コンテスト
ユーザー 高橋ゆに
提出日時 2025-08-09 12:14:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 978 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 137,440 KB
最終ジャッジ日時 2025-09-09 17:10:05
合計ジャッジ時間 14,379 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

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