結果

問題 No.2330 Eat Slime
ユーザー navel_tosnavel_tos
提出日時 2023-05-30 22:50:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,421 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 173,452 KB
最終ジャッジ日時 2024-06-08 20:45:49
合計ジャッジ時間 6,698 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
58,368 KB
testcase_01 AC 39 ms
52,352 KB
testcase_02 AC 40 ms
52,224 KB
testcase_03 AC 38 ms
52,608 KB
testcase_04 AC 50 ms
61,312 KB
testcase_05 AC 40 ms
52,352 KB
testcase_06 AC 41 ms
52,864 KB
testcase_07 TLE -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#MMA Contest 015 I

'''
一番左のスライムを食べる。
食べた後、左からi番目のスライムがBiならボーナス獲得。
最適化しろ。

愚直にシミュレーションしたいが、いやまて、制約がすごいことになっているぞ。
スライドさせたら答え出たりしないかな。

無理だな。捨て。

■AfterContest
畳み込みで解ける事が分かったので畳み込みます。
事前にスライムの配列を反転させておき、各色ごとに一致時にもらえる点数の配列も用意しておけば
各色で畳み込んで結果を合成することでACできそう。やってみよう。
'''
#MOD = 998244353 にのみ対応したFFT。それ以外では機能しません。
class NTT_998244353:
    def __init__(self,MOD=998244353): self._MOD=998244353
    def _FFT(self,f,fft_len,IDFT=False):
        h=0
        while 2**h < max(len(f),fft_len): h+=1
        f+=[0]*(2**h - len(f)); P=pow(3,119*2**(23-h),self._MOD)
        if IDFT: P=pow(P,2**h-1,self._MOD); rev=pow(2**h,self._MOD-2,self._MOD)
        for i in range(2**h):  #バタフライ演算の並び替え
            j=0
            for k in range(h): j|=(i>>k&1)<<(h-1-k)
            if i<j: f[i],f[j]=f[j],f[i]
        for x in range(h):
            b=2**x; Q=pow(P,2**(h-x-1),self._MOD); W=1  #W=Q^j
            for j in range(b):
                for k in range(0,2**h,2*b):
                    s,t=f[j+k],f[j+k+b]*W%self._MOD; f[j+k]=(s+t)%self._MOD; f[j+k+b]=(s-t)%self._MOD
                W=W*Q%self._MOD
        if IDFT:
            for i in range(2**h): f[i]=f[i]*rev%self._MOD
        return f
    def convolve(self,f,g):
        N=1; L=len(f)+len(g)-1
        while N<L: N*=2
        f=self._FFT(f,N); g=self._FFT(g,N); h=[f[i]*g[i]%self._MOD for i in range(N)]
        return self._FFT(h,N,True)[:L]


f=lambda:list(map(int,input().split()))
NTT=NTT_998244353()

#入力受取  Cは反転  Color[i][j]: 色iがjにあれば1(True)
N,M,X=f(); C=f()[::-1]
Color=[[0]*N for _ in range(5)]; Score=[[0]*N for _ in range(5)]
for _ in range(M): a,b,y=f(); Score[b-1][a-1]+=y
for i in range(N): Color[C[i]-1][i]=1

#順に畳み込み
Convolved=[]
for i in range(5): Convolved.append(NTT.convolve(Color[i],Score[i]))
Result=[sum(Convolved[i][j] for i in range(5)) for j in range(len(Convolved[1]))][N-1::-1]+[0]
for i in range(N+1): Result[i]+=X*i
print(max(Result))
0