結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー |
![]() |
提出日時 | 2024-08-30 23:12:15 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 559 bytes |
コンパイル時間 | 379 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 77,496 KB |
最終ジャッジ日時 | 2024-08-30 23:12:19 |
合計ジャッジ時間 | 4,454 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 WA * 1 |
ソースコード
n,W=map(int,input().split())X=10**20M=998244353L=10000R=10000+10000q1=[0]*(L+1+R)q2=[0]*(L+1+R)q3=[-X]*(L+1+R)q1[0]=1q2[0]=1q3[0]=0for _ in range(n):v,w=map(int,input().split())for i in [range(-L,R+1),reversed(range(-L,R+1))][w>0]:if q1[i]:q1[i+w]=1if q3[i+w]<q3[i]+v:q2[i+w]=1q3[i+w]=q3[i]+velif q3[i+w]==q3[i]+v:q2[i+w]+=q2[i]q2[i+w]%=MV=-Xfor i in range(-L,W+1):if q1[i]:V=max(V,q3[i])c=0for i in range(-L,W+1):if q1[i] and q3[i]==V:c+=q2[i]c%=Mprint(V,c)