結果

問題 No.3713 海底探索
ユーザー LyricalMaestro
提出日時 2026-10-12 01:54:03
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 47 ms / 2,000 ms
+ 878µs
コード長 849 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 67 ms
コンパイル使用メモリ 81,588 KB
実行使用メモリ 76,520 KB
最終ジャッジ日時 2026-10-12 01:54:11
合計ジャッジ時間 3,041 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

MAX_INT = 10 ** 18

def main():
    N, A, B = map(int, input().split())
    xy = []
    for _ in range(N):
        x, y = map(int, input().split())
        xy.append((x, y))

    dp = [[MAX_INT ] * (A + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for x, y in xy:
        new_dp = [[MAX_INT ] * (A + 1) for _ in range(N + 1)]

        for n in range(N + 1):
            for a in range(A + 1):
                new_dp[n][a] = min(new_dp[n][a], dp[n][a])

                if n + 1 <= N and a + x <= A:
                    new_dp[n + 1][a + x] = min(new_dp[n + 1][a + x], dp[n][a] + y)

        dp = new_dp

    answer = 0
    for n in range(N + 1):
        for a in range(A + 1):
            if dp[n][a] <= B:
                answer = max(answer, n)
    print(answer)

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