Edit

【pythonでABC182を解説】D - Wandering

問題概要

問題ページ

D - Wandering
D - Wandering

問題ページへ移動する

問題文

数列 \(A_1, A_2, A_3, \dots, A_N\) が与えられます。 この数列は負の要素を含むかもしれません。
数直線上の座標 \(0\) に置かれているロボットが、以下の動作を順に行います。

  • 正の向きに \(A_1\) 進む。
  • 正の向きに \(A_1\) 進み、正の向きに \(A_2\) 進む。
  • 正の向きに \(A_1\) 進み、正の向きに \(A_2\) 進み、正の向きに \(A_3\) 進む。

\(\hspace{140pt} \vdots\)

  • 正の向きに \(A_1\) 進み、正の向きに \(A_2\) 進み、正の向きに \(A_3\) 進み、\(\dots\) 、正の向きに \(A_N\) 進む。

動作開始時から終了時までのロボットの座標の最大値を求めてください。

制約

  • \(1 \le N \le 200000\)
  • \(-10^8 \le A_i \le 10^8\)
  • 入力はすべて整数

問題の考察

ACコード

import sys
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [0] + list(map(int, readline().split()))
    sa = list(itertools.accumulate(a))
    ssa = list(itertools.accumulate(sa))
    mx = 0
    t_mx = 0
    for i in range(1, n + 1):
        mx = max(mx, sa[i])
        t_mx = max(t_mx, ssa[i - 1] + mx)
    print(t_mx)


if __name__ == '__main__':
    solve()

-Edit
-