結果

問題 No.2329 Nafmo、イカサマをする
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:31:48
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,662 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 82,064 KB
実行使用メモリ 54,364 KB
最終ジャッジ日時 2025-04-16 15:36:39
合計ジャッジ時間 2,813 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    K = int(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N])) if N >0 else []
    
    if N == 0:
        print(0)
        return
    
    A_sorted = sorted(A)
    min_A = A_sorted[0]
    max_A = A_sorted[-1]
    
    memo = {}
    
    def dfs(sum_val, count):
        if (sum_val, count) in memo:
            return memo[(sum_val, count)]
        if count == K:
            return sum_val
        max_val = sum_val  # not draw
        t = K - count
        
        # Calculate s_candidate
        s_candidate = min(max_A * t, M - sum_val)
        if s_candidate >= t * min_A and s_candidate <= max_A * t:
            new_sum = sum_val + s_candidate
            new_count = count + t
            if new_count > K:
                new_count = K
            current = dfs(new_sum, new_count)
            if current > max_val:
                max_val = current
        else:
            # Try to draw one card
            max_possible = M - sum_val
            if max_possible >= 0:
                idx = bisect.bisect_right(A_sorted, max_possible) -1
                if idx >=0:
                    a = A_sorted[idx]
                    new_sum = sum_val + a
                    if new_sum <= M:
                        current = dfs(new_sum, count +1)
                        if current > max_val:
                            max_val = current
        memo[(sum_val, count)] = max_val
        return max_val
    
    result = dfs(0, 0)
    print(result)

if __name__ == "__main__":
    main()
0