結果
問題 |
No.1247 ブロック登り
|
ユーザー |
|
提出日時 | 2021-03-04 15:34:00 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,020 bytes |
コンパイル時間 | 155 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 126,508 KB |
最終ジャッジ日時 | 2024-10-04 23:30:37 |
合計ジャッジ時間 | 5,400 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 8 TLE * 1 -- * 17 |
ソースコード
def main2(n,k,a): inf=float('inf') dpl0=[[-inf]*n for _ in range(n)] dpl1=[[-inf]*n for _ in range(n)] dpr0=[[-inf]*n for _ in range(n)] dpr1=[[-inf]*n for _ in range(n)] for i in range(n): if i>0:dpl0[i-1][i]=k*a[i]+(k-1)*a[i-1] if i<n-1:dpr0[i][i+1]=k*a[i]+(k-1)*a[i+1] ans=[-inf]*n lrary=[{} for _ in range(k)] for j in range(k-1,-1,-1): dpl2=[[-inf]*n for _ in range(n)] dpr2=[[-inf]*n for _ in range(n)] ary=lrary.pop() for key,v in ary.items(): f,l,r=key if f: dpr0[l][r]=max(dpr0[l][r],v) else: dpl0[l][r]=max(dpl0[l][r],v) for l in range(n): for r in range(l,n): if k+1-j<r+1-l:break if dpl0[l][r]!=-inf: # dpl0[l][r]からの遷移。 if j-2>=0:dpl2[l][r]=max(dpl2[l][r],dpl0[l][r]) if j-1>=0 and l>0:dpl1[l-1][r]=max(dpl1[l-1][r],dpl0[l][r]+a[l-1]*(j-1)) # l->rへの移動 if j-(r-l)>=0: if (1,l,r)in lrary[j-(r-l)]: lrary[j-(r-l)][1,l,r]=max(lrary[j-(r-l)][1,l,r],dpl0[l][r]) else: lrary[j-(r-l)][1,l,r]=dpl0[l][r] else: ans[l+j]=max(ans[l+j],dpl0[l][r]) if dpr0[l][r]!=-inf: # dpr0[l][r]からの遷移。 if j-2>=0:dpr2[l][r]=max(dpr2[l][r],dpr0[l][r]) if j-1>=0 and r<n-1:dpr1[l][r+1]=max(dpr1[l][r+1],dpr0[l][r]+a[r+1]*(j-1)) # l<-rへの移動 if j-(r-l)>=0: if (0,l,r)in lrary[j-(r-l)]: lrary[j-(r-l)][0,l,r]=max(lrary[j-(r-l)][0,l,r],dpr0[l][r]) else: lrary[j-(r-l)][0,l,r]=dpr0[l][r] else: ans[r-j]=max(ans[r-j],dpr0[l][r]) dpl0,dpl1=dpl1,dpl2 dpr0,dpr1=dpr1,dpr2 for l in range(n): for r in range(l,n): ans[l]=max(ans[l],dpl0[l][r]) ans[r]=max(ans[r],dpr0[l][r]) return ans if __name__=='__main__': n,k=map(int,input().split()) a=list(map(int,input().split())) ret2=main2(n,k,a) print(*ret2,sep='\n')