結果
問題 |
No.324 落ちてた閉路グラフ
|
ユーザー |
![]() |
提出日時 | 2015-12-17 13:38:08 |
言語 | PyPy2 (7.3.15) |
結果 |
AC
|
実行時間 | 394 ms / 5,000 ms |
コード長 | 651 bytes |
コンパイル時間 | 406 ms |
コンパイル使用メモリ | 76,860 KB |
実行使用メモリ | 79,264 KB |
最終ジャッジ日時 | 2024-11-15 19:34:03 |
合計ジャッジ時間 | 6,261 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
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))