結果

問題 No.1334 Multiply or Add
ユーザー maspy
提出日時 2021-01-08 22:03:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 1,809 ms / 2,000 ms
コード長 1,216 bytes
コンパイル時間 992 ms
コンパイル使用メモリ 12,800 KB
実行使用メモリ 29,864 KB
最終ジャッジ日時 2024-11-16 11:50:49
合計ジャッジ時間 30,214 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
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