結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー |
![]() |
提出日時 | 2024-08-30 23:23:30 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 614 bytes |
コンパイル時間 | 548 ms |
コンパイル使用メモリ | 82,468 KB |
実行使用メモリ | 77,580 KB |
最終ジャッジ日時 | 2024-08-30 23:23:35 |
合計ジャッジ時間 | 4,067 ms |
ジャッジサーバーID (参考情報) |
judge3 / 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 v,w in sorted([tuple(map(int,input().split())) for i in range(n)],key=lambda p:p[1]):for i in [range(-L,R+1),reversed(range(-L,R+1))][w>0]:if q1[i] and -L<=i+w<=R: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)