結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー |
![]() |
提出日時 | 2024-08-30 22:35:42 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 649 bytes |
コンパイル時間 | 257 ms |
コンパイル使用メモリ | 82,528 KB |
実行使用メモリ | 77,396 KB |
最終ジャッジ日時 | 2024-08-30 22:35:46 |
合計ジャッジ時間 | 4,010 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 WA * 5 |
ソースコード
n,W=map(int,input().split())X=10**20M=998244353L=10000q1=[0]*(L*2+1)q2=[0]*(L*2+1)q3=[-X]*(L*2+1)q1[0]=1q2[0]=1q3[0]=0p1=0p2=0for _ in range(n):v,w=map(int,input().split())if w==0:if v>0:p1+=velif v==0:p2+=1continuefor i in [range(-L,L+1),reversed(range(-L,L+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+p1,(c*pow(2,p2,M))%M)