結果

問題 No.1334 Multiply or Add
ユーザー gew1fw
提出日時 2025-06-12 16:21:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 882 bytes
コンパイル時間 443 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 104,700 KB
最終ジャッジ日時 2025-06-12 16:21:19
合計ジャッジ時間 7,112 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 49 WA * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

n = int(input())
a = list(map(int, input().split()))

if n == 0:
    print(0)
    exit()

# Compute the product of all elements modulo MOD
product_all = 1
for num in a:
    product_all = (product_all * num) % MOD

# Compute the dynamic programming solution
max_sum = a[0]
current_product = a[0]

for i in range(1, n):
    option_add = max_sum + a[i]
    option_multiply = (max_sum - current_product) + (current_product * a[i])
    
    if option_add > option_multiply:
        new_max_sum = option_add
        new_current_product = a[i]
    else:
        new_max_sum = option_multiply
        new_current_product = (current_product * a[i]) % MOD
    
    max_sum = new_max_sum
    current_product = new_current_product

# The maximum value is the larger of the DP result and the product of all elements
max_val = max(max_sum % MOD, product_all)
print(max_val % MOD)
0