結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー |
![]() |
提出日時 | 2024-08-30 23:28:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 177 ms / 2,000 ms |
コード長 | 578 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 77,752 KB |
最終ジャッジ日時 | 2024-09-26 14:37:40 |
合計ジャッジ時間 | 4,818 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
n,W=map(int,input().split()) X=10**20 M=998244353 L=10000 R=10000+10000 q1=[0]*(L+1+R) q2=[0]*(L+1+R) q3=[-X]*(L+1+R) q1[0]=1 q2[0]=1 q3[0]=0 for _ 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] and -L<=i+w<=R: q1[i+w]=1 if q3[i+w]<q3[i]+v: q2[i+w]=q2[i] q3[i+w]=q3[i]+v elif q3[i+w]==q3[i]+v: q2[i+w]+=q2[i] q2[i+w]%=M V=-X for i in range(-L,W+1): if q1[i]: V=max(V,q3[i]) c=0 for i in range(-L,W+1): if q1[i] and q3[i]==V: c+=q2[i] c%=M print(V,c)