結果
問題 | No.2026 Yet Another Knapsack Problem |
ユーザー |
|
提出日時 | 2022-04-22 14:45:42 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,522 bytes |
コンパイル時間 | 186 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 144,272 KB |
最終ジャッジ日時 | 2024-07-19 12:50:06 |
合計ジャッジ時間 | 25,079 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 TLE * 7 |
ソースコード
from typing import ListINF = 1 << 60class RangeMaxSegmentTree:_n : int_dat : List[int]def __init__(self, dat: List[int]) -> None:self._n = len(dat)self._dat = [0] * self._n + datfor i in reversed(range(1, self._n)):self._dat[i] = max(self._dat[2 * i], self._dat[2 * i + 1])def max(self, l : int, r : int) -> int:l += self._nr += self._nres = -INFwhile l < r:if l & 1:res = max(res, self._dat[l])l += 1if r & 1:r -= 1res = max(res, self._dat[r])l >>= 1r >>= 1return resN = int(input())items = [(int(0), int(0))]for _ in range(N):c, v = map(int, input().split())items.append((c, v))dp = [[-INF] * (N + 1) for i in range(N + 1)]dp[0][0] = 0for i in reversed(range(1, N + 1)):max_num = min(N, N // i)max_sum = Nc, v = items[i]# dp[num][sum] = max{ pd[num-p][sum-p*i]-(num-p)*v[i] | 0<=p<=c[i] } ⋃ {-∞} + num*v[i]for num in range(max_num + 1):for sum in range(i if num else max_sum + 1):max_p = min(max_num - num, (max_sum - sum) // i)seg = RangeMaxSegmentTree([dp[num + p][sum + i * p] - (num + p) * v for p in range(max_p + 1)])for p in range(max_p + 1):dp[num + p][sum + i * p] = seg.max(max(0, p - c), p + 1) + (num + p) * vfor k in range(1, N + 1):print(max(dp[k]))