結果

問題 No.2329 Nafmo、イカサマをする
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:13:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,376 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 57,204 KB
最終ジャッジ日時 2025-04-15 21:19:29
合計ジャッジ時間 2,967 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def solve():
    import sys
    N, M, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    A.sort()
    max_A_val = A[-1] if N > 0 else 0

    from functools import lru_cache

    @lru_cache(maxsize=None)
    def dfs(s, r):
        if r == 0:
            return s if s <= M else -1
        max_val = s if s <= M else -1
        if N == 0:
            return max_val
        for t in range(0, r):
            required = s + t * max_A_val
            if required > M:
                continue
            remaining_for_x = M - required
            max_possible_x = min(max_A_val, remaining_for_x)
            if max_possible_x < 0:
                continue
            idx = bisect.bisect_right(A, max_possible_x) - 1
            if idx < 0:
                continue
            x = A[idx]
            new_s_current = s + x
            new_s_after_t = new_s_current + t * max_A_val
            if new_s_after_t > M:
                continue
            remaining_steps = r - 1 - t
            next_val = dfs(new_s_after_t, remaining_steps)
            if next_val != -1:
                if next_val > max_val:
                    max_val = next_val
        return max_val if max_val <= M else -1

    if N == 0:
        print(0)
        return
    result = dfs(0, K)
    print(result if result != -1 else 0)

solve()
0