結果
問題 | No.1334 Multiply or Add |
ユーザー |
![]() |
提出日時 | 2021-01-08 22:00:44 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 964 bytes |
コンパイル時間 | 358 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 109,952 KB |
最終ジャッジ日時 | 2024-11-16 11:43:54 |
合計ジャッジ時間 | 9,786 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 68 WA * 3 |
ソースコード
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:p = 1for x in A:p = p * x % MODreturn p# 以下、総積が小さい場合。# 途中経過は、"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))