結果

問題 No.3129 Multiple of Twin Subarray
ユーザー urunea
提出日時 2025-05-01 16:09:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 344 ms / 2,000 ms
コード長 1,423 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,448 KB
実行使用メモリ 231,396 KB
最終ジャッジ日時 2025-05-01 16:09:51
合計ジャッジ時間 11,455 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from itertools import accumulate

N=int(input())
A=list(map(int, input().split()))
to_right=list(accumulate(A))
to_left=list(accumulate(A[::-1]))[::-1]

if N == 2:
    print(A[0]*A[1])
    exit()

leftM=[]
rightM=[]
leftm=[]
rightm=[]
heapq.heapify(leftM)
heapq.heapify(rightM)
heapq.heapify(leftm)
heapq.heapify(rightm)

mem1=[A[0]]
mem2=[A[0]]
rmem1=[A[-1]]
rmem2=[A[-1]]

heapq.heappush(leftM, -A[0])
heapq.heappush(rightM, -A[-1])
heapq.heappush(leftm, A[0])
heapq.heappush(rightm, A[-1])

for i in range(1,N-1):
    mem1.append(max(to_right[i]-leftm[0], to_right[i]))
    mem2.append(min(to_right[i]+leftM[0],to_right[i]))
    heapq.heappush(leftM, -to_right[i])
    heapq.heappush(leftm, to_right[i])

for i in range(-2,-N,-1):
    rmem1.append(max(to_left[i]-rightm[0], to_left[i]))
    rmem2.append(min(to_left[i]+rightM[0], to_left[i]))
    heapq.heappush(rightM, -to_left[i])
    heapq.heappush(rightm, to_left[i])

to_rightmax = list(accumulate(mem1, lambda x,y: max(x,y))) 
to_rightmin = list(accumulate(mem2, lambda x,y: min(x,y)))
to_leftmax = list(accumulate(rmem1, lambda x,y: max(x,y)))[::-1]
to_leftmin = list(accumulate(rmem2, lambda x,y: min(x,y)))[::-1]

ans=0
for i in range(N-1):
    ans = max(ans, to_rightmax[i]*to_leftmax[i])
    ans = max(ans, to_rightmax[i]*to_leftmin[i])
    ans = max(ans, to_rightmin[i]*to_leftmax[i])
    ans = max(ans, to_rightmin[i]*to_leftmin[i])

print(ans)
0