結果

問題 No.3014 岩井満足性問題
ユーザー D M
提出日時 2025-02-04 10:37:30
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 502 ms / 3,000 ms
コード長 1,489 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 82,348 KB
実行使用メモリ 78,080 KB
最終ジャッジ日時 2025-02-04 10:37:39
合計ジャッジ時間 5,718 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    # 入力は sys.stdin.buffer.read() で一括読み込み（高速）
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    try:
        N = int(next(it))
        D = int(next(it))
        K = int(next(it))
    except StopIteration:
        return
    A = [0] * N
    for i in range(N):
        A[i] = int(next(it))
    C = [0] * N
    for i in range(N):
        C[i] = int(next(it))

    INF = -10 ** 18  # 達成不可能な値（満足度の下限より十分小さい）
    # dp[d][b] = 採用済み問題が d 個，合計美しさが b (b>=K は b=K とする) のときの最大満足度
    dp = [[INF] * (K + 1) for _ in range(D + 1)]
    dp[0][0] = 0

    # 各問題について更新（0/1ナップザック方式）
    for i in range(N):
        a = A[i]
        c = C[i]
        # 採用済み問題数 d を D-1 から 0 まで逆順に更新
        for d in range(D - 1, -1, -1):
            cur = dp[d]
            nxt = dp[d + 1]
            for b in range(K + 1):
                val = cur[b]
                if val == INF:
                    continue
                nb = b + c
                if nb >= K:
                    nb = K
                cand = val + a
                if cand > nxt[nb]:
                    nxt[nb] = cand

    ans = dp[D][K]
    if ans == INF:
        sys.stdout.write("No")
    else:
        sys.stdout.write(str(ans))


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