結果

問題 No.115 遠足のおやつ
ユーザー gorugo30
提出日時 2021-02-27 14:38:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 129 ms / 5,000 ms
コード長 822 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 84,608 KB
最終ジャッジ日時 2025-01-03 02:02:50
合計ジャッジ時間 4,528 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, D, K = map(int, input().split())
if N == 1:
    if D == 1 and K == 1:
        print(1)
    else:
        print(-1)
    exit()

dp = [[[False] * (D + 1) for j in range(K + 1)] for i in range(N)]
dp[N - 1][0][0] = True
if N <= D:
    dp[N - 1][1][N] = True
for i in range(N - 2, -1, -1):
    for j in range(K + 1):
        for k in range(D + 1):
            dp[i][j][k] |= dp[i + 1][j][k]
    for j in range(1, K + 1):
        for k in range(D + 1):
            if k + i + 1 <= D:
                dp[i][j][k + i + 1] |= dp[i + 1][j - 1][k]
ans = []
for i in range(N - 1):
    k = len(ans)
    d = sum(ans)
    if 0 <= K - k - 1 <= K and 0 <= D - d - i - 1 <= D and dp[i + 1][K - k - 1][D - d - i - 1]:
        ans.append(i + 1)
if sum(ans) + N == D:
    ans.append(N)
if len(ans) == 0:
    print(-1)
else:
    print(*ans)
0