結果
問題 | No.1334 Multiply or Add |
ユーザー |
|
提出日時 | 2021-01-08 22:38:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 1,902 bytes |
コンパイル時間 | 1,064 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 119,168 KB |
最終ジャッジ日時 | 2024-11-16 13:47:21 |
合計ジャッジ時間 | 8,627 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 |
ソースコード
N = int(input())A = list(map(int,input().split()))mod = 10**9 + 7check = 1for i in range(N):check *= A[i]if check>2**20:check = 2**20breakif check==2**20:L = -1R = Nfor i in range(N):if A[i]>1:if L==-1:L = iR = ires = 0if L!=-1:res = L + (N-1-R)tmp = 1for i in range(L,R+1):tmp *= A[i]tmp %= modres += tmpres %= modprint(res)else:comp = []tmp = 1flag = Falsefor i in range(N):if A[i]==1:if flag:comp.append(tmp)flag = Falsecomp.append(1)else:if not flag:tmp = A[i]flag = Trueelse:tmp *= A[i]tmp %= modif flag:comp.append(tmp)n = len(comp)L = -1R = Nfor i in range(n):if comp[i]!=1:if L==-1:L = iR = iif L==-1:res = Nprint(res)elif L==R:res = sum(comp)print(res%mod)else:comp = [comp[i] for i in range(L,R+1)]new_comp = []for i in range(len(comp)):if comp[i]!=1:new_comp.append(i)res = 0m = len(new_comp)#print(comp)#print(new_comp)for i in range(2**(m-1)):tmp = L + (n-1-R)tmp_prod = comp[new_comp[0]]for j in range(m-1):if i>>j & 1:tmp_prod *= comp[new_comp[j+1]]else:tmp += tmp_prod + new_comp[j+1] - new_comp[j] - 1tmp_prod = comp[new_comp[j+1]]tmp += tmp_prod#print(tmp,L,R,n,tmp_prod)res = max(res,tmp)print(res)