結果

問題 No.2330 Eat Slime
ユーザー navel_tos
提出日時 2023-05-30 22:50:27
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,421 bytes
コンパイル時間 368 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 292,704 KB
最終ジャッジ日時 2024-12-28 13:14:18
合計ジャッジ時間 111,926 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

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