結果

問題 No.115 遠足のおやつ
コンテスト
ユーザー norioc
提出日時 2026-02-25 10:21:05
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 77 ms / 5,000 ms
コード長 975 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 259 ms
コンパイル使用メモリ 78,164 KB
実行使用メモリ 78,628 KB
最終ジャッジ日時 2026-02-25 10:21:10
合計ジャッジ時間 4,520 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def to_list(cons_cell: tuple) -> list:
    res = []
    x = cons_cell
    while x is not None:
        a, x = x
        res.append(a)

    return res


def recur_dp(p, dp):
    if p == len(costs):
        if (K, D) in dp:
            return True, K, D, None

        return False, 0, 0, None

    cost = costs[p]
    pp = dp.copy()
    dp, pp = pp, dp
    for k, d in pp:
        if k == K: continue
        if d + cost > D: continue
        dp.add((k+1, d+cost))

    ok, rk, rd, path = recur_dp(p+1, dp)
    if not ok:
        return ok, rk, rd, path

    # 復元
    for k, d in pp:
        if k+1 == rk and d+cost == rd:
            return ok, rk-1, rd-cost, (cost, path)

    return ok, rk, rd, path


N, D, K = map(int, input().split())
costs = list(reversed(range(1, N+1)))  # 辞書順参照を求めるので逆順にする

dp = {(0, 0)}  # (個数, 総和)
ok, _, _, path = recur_dp(0, dp)
if ok:
    ans = to_list(path)[::-1]
    print(*ans)
else:
    print(-1)
0