結果
問題 |
No.2889 Rusk
|
ユーザー |
|
提出日時 | 2025-06-29 14:42:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 432 ms |
コンパイル使用メモリ | 82,712 KB |
実行使用メモリ | 142,724 KB |
最終ジャッジ日時 | 2025-06-29 14:42:29 |
合計ジャッジ時間 | 9,614 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
import sys input=sys.stdin.readline MI=lambda:map(int,input().split()) li=lambda:list(MI()) ii=lambda:int(input()) n=ii() a=li() b=li() c=li() i1=[b[i]-a[i] for i in range(n)] i2=[c[i]-b[i] for i in range(n)] p1=[0]*(n+1) p2=[0]*(n+1) for i in range(n): p1[i+1]=p1[i]+i1[i] p2[i+1]=p2[i]+i2[i] m1=0 cur=0 for v in i1: cur+=v if cur<0: cur=0 if cur>m1: m1=cur lmx=[0]*n cur=0 best=0 for i,v in enumerate(i1): cur+=v if cur<0: cur=0 if cur>best: best=cur lmx[i]=best rmx=[0]*n cur=0 best=0 for i in range(n-1,-1,-1): cur+=i1[i] if cur<0: cur=0 if cur>best: best=cur rmx[i]=best m2=0 for i in range(n-1): s=lmx[i]+rmx[i+1] if s>m2: m2=s suf=[0]*(n+2) suf[n]=p1[n] for i in range(n-1,0,-1): if p1[i]>suf[i+1]: suf[i]=p1[i] else: suf[i]=suf[i+1] f=-p1[0] M=[0]*(n+1) M[1]=f-p2[0] for i in range(2,n+1): v=-p1[i-1] if v>f: f=v g=f-p2[i-1] if M[i-1]>g: M[i]=M[i-1] else: M[i]=g m3=0 for i in range(1,n+1): v=suf[i]+p2[i]+M[i] if v>m3: m3=v extra=m1 if m2>extra: extra=m2 if m3>extra: extra=m3 sA=sum(a) print(sA+extra)