結果
問題 | No.1848 Long Prefixes |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-07 14:50:26 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 758 bytes |
コンパイル時間 | 123 ms |
コンパイル使用メモリ | 82,124 KB |
実行使用メモリ | 126,484 KB |
最終ジャッジ日時 | 2024-06-29 07:58:44 |
合計ジャッジ時間 | 4,537 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 11 WA * 29 |
ソースコード
def z_algo(p):n=len(p)Z=[0]*nZ[0]=ni=1j=0while i<n:while i+j<n and p[i]==p[i+j]:j+=1Z[i]=jif j==0:i+=1continuek=1while k<j and k+Z[k]<j:Z[i+k]=Z[k]k+=1i+=kj-=kreturn ZN=int(input())A=list(map(int,input().split()))S=input()M=10**9+7half=(M+1)//2p=[('#',100)]*(N)cum_sum=[0]*(N+1)for i in range(N-1):p[i]=(S[i+1],A[i+1])cum_sum[i+1]=(cum_sum[i]+A[i+1])%Mcum_sum[N]=cum_sum[N-1]Z=z_algo(p)ans=0for i in range(N):if S[i]!=S[0]:continueif A[i]<A[0]:ans+=((A[i]+1)*A[i])//2ans%=Melse:ans+=(A[0]*(A[i]-A[0]))ans%=Mans+=(A[0]*(A[0]+1))//2ans%=Mans+=cum_sum[Z[i]]if i+Z[i]+1<N and S[i+1+Z[i]]==S[1+Z[i]]:ans+=min(A[i+1+Z[i]],A[1+Z[i]])ans%=Mprint(ans)