結果

問題 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)
0