結果
問題 | No.1334 Multiply or Add |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesMOD = 1_000_000_007def main(A):# 総積がでかいなら、端の 1 以外はまとめてしまうp = 1INF = 1 << 20for x in A:p = min(p * x, INF)if p == INF:add = 0for x in A:if x == 1:add += 1else:breakfor x in A[::-1]:if x == 1:add += 1else:breakp = 1for x in A:p = p * x % MODreturn (p + add) % MOD# 以下、総積が小さい場合。# 途中経過は、"a + b*" or "a+" と書ける。# b ごとに optimal な a を持つdp = {}max_v = 0for x in A:newdp = {}vv = 0for 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 = newdpmax_v = max(vv, max_v + x)return max_vA = tuple(map(int, read().split()))[1:]print(main(A))