結果

問題 No.2329 Nafmo、イカサマをする
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:27:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,259 bytes
コンパイル時間 235 ms
コンパイル使用メモリ 81,680 KB
実行使用メモリ 163,760 KB
最終ジャッジ日時 2025-04-16 15:31:27
合計ジャッジ時間 5,045 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 -- * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from heapq import heappush, heappop

def compute_D(S, t, T):
    if T <= 0:
        return 0
    S = list(set(S))  # Remove duplicates to optimize
    heap = []
    heappush(heap, (0, 0))  # (current_sum, steps)
    min_sum = None

    for step in range(t):
        next_heap = []
        while heap:
            current_sum, steps = heappop(heap)
            if steps == t:
                if current_sum >= T and (min_sum is None or current_sum < min_sum):
                    min_sum = current_sum
                continue
            if steps > step:
                continue  # Only process steps up to the current step
            for s in S:
                new_sum = current_sum + s
                new_steps = steps + 1
                if new_steps > t:
                    continue
                heappush(next_heap, (new_sum, new_steps))
        heap = next_heap
        if not heap:
            break

    # Check remaining elements in heap for exact t steps
    while heap:
        current_sum, steps = heappop(heap)
        if steps == t and current_sum >= T:
            if min_sum is None or current_sum < min_sum:
                min_sum = current_sum

    return min_sum if min_sum is not None else float('inf')

def main():
    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
    x = max(A)
    S = [x - a for a in A]
    max_possible = 0

    for t in range(0, K+1):
        if t == 0:
            current_sum = 0
            if current_sum <= M and current_sum > max_possible:
                max_possible = current_sum
            continue

        max_t_sum = x * t
        if max_t_sum <= M:
            if max_t_sum > max_possible:
                max_possible = max_t_sum
            continue

        T = max_t_sum - M
        D = compute_D(S, t, T)
        if D == float('inf'):
            continue  # No valid combination found
        candidate = max_t_sum - D
        if candidate <= M and candidate > max_possible:
            max_possible = candidate

    print(max_possible)

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