結果
問題 | No.2026 Yet Another Knapsack Problem |
ユーザー |
|
提出日時 | 2022-04-24 13:48:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 6,174 ms / 10,000 ms |
コード長 | 2,561 bytes |
コンパイル時間 | 200 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 143,736 KB |
最終ジャッジ日時 | 2024-07-21 22:37:26 |
合計ジャッジ時間 | 52,512 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import gcdfrom fractions import Fractioninput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())local_test = Falsedef random_test(N):item = [(N,random.randint(-10**2,10**2))]for i in range(1,N):c = random.randint(1,2)v = random.randint(-10**2,10**2)item.append((c,v))return itemdef solve_slow(N,item):dp = [[-INF]*(N+1) for w in range(N+1)]dp[0][0] = 0for i in range(N):c,v = item[i]for w in range(N+1)[::-1]:for k in range(N+1)[::-1]:for use in range(c+1):if w+use*(i+1) <= N and k+use <= N:dp[w+use*(i+1)][k+use] = max(dp[w+use*(i+1)][k+use],dp[w][k]+use*v)return [max(dp[w][k] for w in range(N+1)) for k in range(1,N+1)]def solve(N,item):dp = [[-INF]*(N+1) for i in range(N+1)]dp[0][0] = 0for i in range(N)[::-1]:c,v = item[i]k_max = N//(i+1)for w_start in range(i+1):for k_start in range(k_max+1):deq = deque()for k in range(k_start,k_max+1):w = w_start + (k-k_start) * (i+1)if N < w:breakif deq and deq[0][1] < k-c:deq.popleft()tmp = dp[w][k] - k * vwhile deq and deq[-1][0] <= tmp:deq.pop()deq.append((tmp,k))dp[w][k] = v*k + deq[0][0]for w_start in range(i+1,N+1):for k_start in range(1):deq = deque()for k in range(k_start,k_max+1):w = w_start + (k-k_start) * (i+1)if N < w:breakif deq and deq[0][1] < k-c:deq.popleft()tmp = dp[w][k] - k * vwhile deq and deq[-1][0] <= tmp:deq.pop()deq.append((tmp,k))dp[w][k] = v*k + deq[0][0]res = [max(dp[w][k] for w in range(N+1)) for k in range(1,N+1)]return resINF = 10**17N = int(input())item = [tuple(mi()) for i in range(N)]print(*solve(N,item),sep="\n")