結果

問題 No.1334 Multiply or Add
ユーザー chineristAC
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
check = 1
for i in range(N):
check *= A[i]
if check>2**20:
check = 2**20
break
if check==2**20:
L = -1
R = N
for i in range(N):
if A[i]>1:
if L==-1:
L = i
R = i
res = 0
if L!=-1:
res = L + (N-1-R)
tmp = 1
for i in range(L,R+1):
tmp *= A[i]
tmp %= mod
res += tmp
res %= mod
print(res)
else:
comp = []
tmp = 1
flag = False
for i in range(N):
if A[i]==1:
if flag:
comp.append(tmp)
flag = False
comp.append(1)
else:
if not flag:
tmp = A[i]
flag = True
else:
tmp *= A[i]
tmp %= mod
if flag:
comp.append(tmp)
n = len(comp)
L = -1
R = N
for i in range(n):
if comp[i]!=1:
if L==-1:
L = i
R = i
if L==-1:
res = N
print(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 = 0
m = 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] - 1
tmp_prod = comp[new_comp[j+1]]
tmp += tmp_prod
#print(tmp,L,R,n,tmp_prod)
res = max(res,tmp)
print(res)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0