結果
問題 | No.2617 容量3のナップザック |
ユーザー |
![]() |
提出日時 | 2024-01-26 22:07:29 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 893 bytes |
コンパイル時間 | 270 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 203,008 KB |
最終ジャッジ日時 | 2024-09-28 08:13:25 |
合計ジャッジ時間 | 4,516 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 10 TLE * 1 -- * 29 |
ソースコード
N,K,seed,a,b,m=map(int,input().split())w=[0]*Nf=seedfor i in range(N):w[i]=f%3+1f=(a*f+b)%mv=[0]*Nfor i in range(N):v[i]=f*w[i]f=(a*f+b)%mw1=[]w2=[]w3=[]for i in range(N):if w[i]==1:w1.append(v[i])if w[i]==2:w2.append(v[i])if w[i]==3:w3.append(v[i])w1.sort(reverse=True)w2.sort(reverse=True)w3.sort(reverse=True)w1+=[0]*max(0,(3*N+10-len(w1)))w2+=[0]*max(0,N+10-len(w2))w3+=[0]*max(0,N+10-len(w3))ans=0res=[0]idx1=0idx2=0tmp=0for i in range(1,K+1):tmp+=w1[idx1]+w1[idx1+1]+w1[idx1+2]idx1+=3while idx2<i and w2[idx2]>=w1[idx1-1]+w1[idx1-2]:tmp+=w2[idx2]-w1[idx1-1]-w1[idx1-2]idx2+=1idx1-=2while idx2>0 and w1[idx1]+w1[idx1+1]>=w2[idx2-1]:tmp+=w1[idx1]+w1[idx1+1]-w2[idx2-1]idx2-=1idx1+=2res.append(tmp)cum3=0for i in range(K+1):ans=max(ans,res[K-i]+cum3)cum3+=w3[i]print(ans)