結果

問題 No.1947 質より種類数
ユーザー lam6er
提出日時 2025-04-15 23:39:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,806 bytes
コンパイル時間 396 ms
コンパイル使用メモリ 82,144 KB
実行使用メモリ 135,036 KB
最終ジャッジ日時 2025-04-15 23:41:04
合計ジャッジ時間 8,666 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 WA * 2 TLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    V = int(input[idx]); idx +=1
    C = int(input[idx]); idx +=1
    
    types = []
    for _ in range(N):
        v = int(input[idx]); idx +=1
        w = int(input[idx]); idx +=1
        types.append((v, w))
    
    # Sort types in descending order of w/v ratio
    types.sort(key=lambda x: -(x[1] / x[0]))
    
    # Initialize DP: dp[k] is a dictionary {sum_v: (sum_w, max_v, max_w)}
    dp = [{} for _ in range(N+1)]
    dp[0][0] = (0, 0, 0)  # 0 types, sum_v=0, sum_w=0, max_v=0, max_w=0
    
    for i in range(N):
        v_i, w_i = types[i]
        # Iterate in reverse to avoid processing the same item multiple times
        for k in range(N, 0, -1):
            current_dp = dp[k-1]
            for sum_v in list(current_dp.keys()):
                sum_w, current_max_v, current_max_w = current_dp[sum_v]
                new_sum_v = sum_v + v_i
                if new_sum_v > V:
                    continue
                new_sum_w = sum_w + w_i
                # Determine the new max ratio
                current_ratio = current_max_w / current_max_v if current_max_v != 0 else 0
                new_type_ratio = w_i / v_i
                if new_type_ratio > current_ratio:
                    new_max_v, new_max_w = v_i, w_i
                else:
                    new_max_v, new_max_w = current_max_v, current_max_w
                # Update the new state
                if new_sum_v not in dp[k] or new_sum_w > dp[k].get(new_sum_v, (0, 0, 0))[0] or \
                    (new_sum_w == dp[k].get(new_sum_v, (0, 0, 0))[0] and (new_max_w / new_max_v if new_max_v !=0 else 0) > (dp[k][new_sum_v][2] / dp[k][new_sum_v][1] if dp[k][new_sum_v][1] !=0 else 0)):
                    dp[k][new_sum_v] = (new_sum_w, new_max_v, new_max_w)
        # Handle the case where this is the first type added (k=1)
        if v_i <= V:
            new_sum_v = v_i
            new_sum_w = w_i
            new_k = 1
            new_max_v, new_max_w = v_i, w_i
            if new_sum_v not in dp[new_k] or new_sum_w > dp[new_k].get(new_sum_v, (0, 0, 0))[0]:
                dp[new_k][new_sum_v] = (new_sum_w, new_max_v, new_max_w)
    
    max_satisfaction = 0
    for k in range(N+1):
        for sum_v in dp[k]:
            sum_w, max_v, max_w = dp[k][sum_v]
            if sum_v > V:
                continue
            remaining = V - sum_v
            if max_v == 0:
                additional = 0
            else:
                additional = (remaining // max_v) * max_w
            satisfaction = k * C + sum_w + additional
            if satisfaction > max_satisfaction:
                max_satisfaction = satisfaction
    print(max_satisfaction)

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