結果

問題 No.37 遊園地のアトラクション
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:53:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 51 ms / 5,000 ms
コード長 1,435 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,436 KB
実行使用メモリ 62,188 KB
最終ジャッジ日時 2025-03-20 20:53:50
合計ジャッジ時間 2,704 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys

    T = int(sys.stdin.readline())
    N = int(sys.stdin.readline())
    c_list = list(map(int, sys.stdin.readline().split()))
    v_list = list(map(int, sys.stdin.readline().split()))

    # Preprocess each attraction to generate viable (time, value) options
    groups = []
    for ci, vi in zip(c_list, v_list):
        options = []
        sum_t = 0
        sum_v = 0
        current_v = vi
        while True:
            sum_t += ci
            sum_v += current_v
            # Break if sum_t exceeds T
            if sum_t > T:
                break
            options.append((sum_t, sum_v))
            current_v = current_v // 2
            if current_v == 0:
                break
        # Filter to keep only time-efficient and value-increasing options
        filtered = []
        max_value = -1
        for t, v in options:
            if v > max_value:
                filtered.append((t, v))
                max_value = v
        groups.append(filtered)

    # Initialize DP array
    dp = [0] * (T + 1)

    # Process each group with group knapsack approach
    for group in groups:
        prev_dp = dp.copy()
        for t, v in group:
            for j in range(T, t - 1, -1):
                if prev_dp[j - t] + v > dp[j]:
                    dp[j] = prev_dp[j - t] + v

    # Find the maximum value within the time limit
    print(max(dp[:T+1]))

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