結果

問題 No.2866 yuusaan's Knapsack
ユーザー LyricalMaestro
提出日時 2025-08-30 01:49:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 257 ms / 2,000 ms
コード長 1,578 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 108,008 KB
最終ジャッジ日時 2025-08-30 01:49:45
合計ジャッジ時間 6,360 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2866

MIN_VALUE = - 10 ** 18
MOD = 998244353

def main():
    N, W =  map(int, input().split())
    vw = []
    for _ in range(N):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(key=lambda x : x[1])

    dp = {0:[0, 1]}
    for v, w in vw:
        new_dp = {}
        for key, values in dp.items():
            value, count = values

            if key not in new_dp:
                new_dp[key] = [MIN_VALUE, 0]
            if new_dp[key][0] < value:
                new_dp[key][0] = value
                new_dp[key][1] = count
            elif new_dp[key][0] == value:
                new_dp[key][1] += count
                new_dp[key][1] %= MOD

            new_key= w + key
            new_value = value + v
            if new_key <= W:
                if new_key not in new_dp:
                    new_dp[new_key] = [MIN_VALUE, 0]
                if new_dp[new_key][0] < new_value:
                    new_dp[new_key][0] = new_value
                    new_dp[new_key][1] = count
                elif new_dp[new_key][0] == new_value:
                    new_dp[new_key][1] += count
                    new_dp[new_key][1] %= MOD

        dp = new_dp

    answer = MIN_VALUE
    ans_count = 0    
    for key, values in dp.items():
        value, count =values
        if answer < value:
            answer = value
            ans_count = count
        elif answer == value:
            ans_count += count
            ans_count %= MOD

    print(answer, ans_count)



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