結果
問題 | No.1334 Multiply or Add |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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))