結果

問題 No.3014 岩井満足性問題
コンテスト
ユーザー ymsksky
提出日時 2025-02-02 13:48:39
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 878 bytes
コンパイル時間 508 ms
コンパイル使用メモリ 82,784 KB
実行使用メモリ 366,428 KB
最終ジャッジ日時 2025-02-02 13:49:01
合計ジャッジ時間 20,411 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 MLE * 1
other AC * 9 WA * 4 TLE * 3 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

INF = float("inf")

N, D, K = map(int, input().split())
al = list(map(int, input().split()))
cl = list(map(int, input().split()))

# dp[i%2][j*K + k]: i個目までを使ってj個で美しさがkのときの最大チ。
# ただしk=Kはkより大きい時も含む
dp = [[-INF] * (K + 1)*(D + 1) for _ in range(2)]
dp[0][0] = 0

for i in range(1, N + 1):
    dp[i%2] = [-INF] * (K + 1)*(D + 1)
    a = al[i - 1]  # 満足度(マイナスあり)
    c = cl[i - 1]  # 美しさ
    dp[i%2][0] = dp[(i - 1)%2][0]
    for j in range(1, min(i + 1, D + 1)):
        for k in range(K + 1):
            # 渡すdp
            dp[i%2][j*K + min(K, k + c)] = max(
                dp[i%2][j*K + min(K, k + c)],
                dp[(i - 1)%2][j*K + min(K, k + c)],
                dp[(i - 1)%2][(j - 1)*K + k] + a,
            )

ans = dp[N%2][D*K + K]
print("No" if ans == -INF else ans)
0