結果
問題 |
No.324 落ちてた閉路グラフ
|
ユーザー |
![]() |
提出日時 | 2015-12-17 13:27:37 |
言語 | Python2 (2.7.18) |
結果 |
TLE
|
実行時間 | - |
コード長 | 554 bytes |
コンパイル時間 | 443 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-09-16 07:31:16 |
合計ジャッジ時間 | 9,885 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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 def solve(b): global dp ret = -INF for i in xrange(1,n): base = b if i==n-1 else 0 dp2 = [-INF] + [max(dp[j]+w[i-1]+base, rs[j]+base) for j in xrange(m)] for j in xrange(m+1): rs[j] = max(dp[j], rs[j]) dp = dp2 ret = max(ret, dp[m]) return ret dp = [-INF]*(m+1); rs = [-INF]*(m+1) dp[1] = 0 rr = solve(w[-1]) dp = [-INF]*(m+1); rs = [-INF]*(m+1) rs[0] = 0 print max(rr, solve(0))