結果
問題 |
No.115 遠足のおやつ
|
ユーザー |
![]() |
提出日時 | 2024-07-17 01:14:36 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 81 ms / 5,000 ms |
コード長 | 1,017 bytes |
コンパイル時間 | 302 ms |
コンパイル使用メモリ | 81,768 KB |
実行使用メモリ | 73,584 KB |
最終ジャッジ日時 | 2024-07-17 01:14:40 |
合計ジャッジ時間 | 3,498 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
def list3(a, b, c, *, val=0): return [[[val] * c for _ in range(b)] for _ in range(a)] N, D, K = map(int, input().split()) dp = list3(N+1, K+1, D+1, val=False) # dp[i][j][k] # i : i 番目まで見た # j : j 個のおかしを選んだ # k : k 円かかった dp[0][0][0] = True a = list(reversed(range(1, N+1))) # お菓子の値段(辞書順に取るので逆順) for i in range(N): for j in range(K+1): # j 個買った for k in range(D+1): # k 円使った dp[i+1][j][k] |= dp[i][j][k] if not dp[i][j][k]: continue if j == K: continue nk = k + a[i] if nk > D: continue dp[i+1][j+1][nk] = True if not dp[N][K][D]: print(-1) exit() # DP復元 ans = [] cnt = K yen = D for i in reversed(range(1, N+1)): if dp[i][cnt][yen]: y = a[i-1] if yen-y >= 0 and dp[i-1][cnt-1][yen-y]: ans.append(N-i+1) cnt -= 1 yen -= y assert cnt == 0 and yen == 0 print(*ans)