結果
問題 |
No.324 落ちてた閉路グラフ
|
ユーザー |
![]() |
提出日時 | 2015-12-17 13:41:10 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 651 bytes |
コンパイル時間 | 507 ms |
コンパイル使用メモリ | 6,940 KB |
実行使用メモリ | 13,980 KB |
最終ジャッジ日時 | 2024-09-16 07:31:26 |
合計ジャッジ時間 | 9,686 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 1 TLE * 1 -- * 32 |
ソースコード
r = lambda: map(int, raw_input().split()) n, m = r() if m<2: print 0 exit(0) w = r() INF = 10**9 rm = range(m) rm1 = range(m+1) def solve(b): dp = r_dp; rs = r_rs ret = -INF for i in xrange(1,n-1): wi = w[i-1] dp2 = [-INF] + [max(dp[j]+wi, rs[j]) for j in rm] for j in rm1: rs[j] = max(dp[j], rs[j]) dp = dp2 ret = max(ret, dp[m]) wi = w[-2] dp2 = [-INF] + [max(dp[j]+wi, rs[j])+b for j in rm] return max(ret, dp2[m]) r_dp = [-INF]*(m+1); r_rs = [-INF]*(m+1) r_dp[1] = 0 rr = solve(w[-1]) r_dp = [-INF]*(m+1); r_rs = [-INF]*(m+1) r_rs[0] = 0 print max(rr, solve(0))