結果

問題 No.1334 Multiply or Add
ユーザー maspy
提出日時 2021-01-08 22:03:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 223 ms / 2,000 ms
コード長 1,216 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 109,952 KB
最終ジャッジ日時 2024-11-16 11:53:39
合計ジャッジ時間 9,716 ms
ジャッジサーバーID
(参考情報)
judge4 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 71
権限があれば一括ダウンロードができます

ソースコード

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 1_000_000_007
def main(A):
# 1
p = 1
INF = 1 << 20
for x in A:
p = min(p * x, INF)
if p == INF:
add = 0
for x in A:
if x == 1:
add += 1
else:
break
for x in A[::-1]:
if x == 1:
add += 1
else:
break
p = 1
for x in A:
p = p * x % MOD
return (p + add) % MOD
#
# "a + b*" or "a+"
# b optimal a
dp = {}
max_v = 0
for x in A:
newdp = {}
vv = 0
for b, a in dp.items():
# a + b * [x] +
vv = max(vv, a + b * x)
# a + b * [x] *
newdp[b * x] = max(newdp.get(b * x, 0), a)
newdp[x] = max(newdp.get(x, 0), max_v)
dp = newdp
max_v = max(vv, max_v + x)
return max_v
A = tuple(map(int, read().split()))[1:]
print(main(A))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0