結果

問題 No.3185 Three Abs
ユーザー navel_tos
提出日時 2025-08-14 21:01:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 646 ms / 2,000 ms
コード長 1,374 bytes
コンパイル時間 250 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 135,836 KB
最終ジャッジ日時 2025-08-14 21:02:10
合計ジャッジ時間 16,288 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3185 Three Abs

def solve(N, A):
    #A[:i], A[i: j], A[j:] に分割する。
    #note: 空区間ができたとき、総和を0としていいか？ → OK 明らかに最適解にならないから
    #でも実装の練習をしたいのでiはvalidな分割のみ認めることにする
    
    #jを全探索するとして、最適な分割点iを前計算しておきたい
    #sum maxとsum minのどちらかで区切ればいいんじゃないか？とエスパー
    #とにもかくにも累積和配列を作る
    C = [0] * (N + 1)
    for i, Ai in enumerate(A):
        C[i + 1] = C[i] + Ai

    #分割は |C[i] - C[0]| + |C[j] - C[i]| + |C[N] - C[j]| と書ける点に注意
    #jを全探索するとして、選べるiは[1, j)の範囲となる
    #j = 2 ～ N - 1を探索する
    Ci_min = Ci_max = C[1] - C[0]
    i_min = i_max = 1
    ans = - 1 << 63
    for j in range(2, N):
        ans = max(ans,
                  abs(Ci_min) + abs(C[j] - C[i_min]) + abs(C[N] - C[j]),
                  abs(Ci_max) + abs(C[j] - C[i_max]) + abs(C[N] - C[j]))
        if C[j] - C[0] < Ci_min:
            Ci_min, i_min = C[j] - C[0], j
        if C[j] - C[0] > Ci_max:
            Ci_max, i_max = C[j] - C[0], j
    return ans


for _ in range( T := int(input()) ):
    print( solve(N := int(input()), A := list(map(int, input().split()))) )
0