結果

問題 No.324 落ちてた閉路グラフ
ユーザー tjake
提出日時 2015-12-17 01:08:32
言語 Python2
(2.7.18)
結果
TLE  
実行時間 -
コード長 610 bytes
コンパイル時間 95 ms
コンパイル使用メモリ 7,040 KB
実行使用メモリ 41,632 KB
最終ジャッジ日時 2024-09-16 06:42:58
合計ジャッジ時間 6,665 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10**7)
r = lambda: map(int, raw_input().split())
n, m = r()
w = r()
INF = 10**9

dp = [[-INF]*(m+1) for i in xrange(n)]
b = w[-1]
def dfs(c, s):
    if s==m:
        return b if c==n-1 else 0
    if c>=n:
        return -INF
    v = dp[c][s]
    if v!=-INF:
        return v
    ret = dfs(c+1, s+1) + w[c]
    for i in xrange(c+2,n):
        ret = max(ret, dfs(i, s+1))
    dp[c][s] = ret
    return ret

a = w[0] + dfs(1, 2)
for i in xrange(2, n):
    a = max(a, dfs(i, 2))
dp = [[-INF]*(m+1) for i in xrange(n)]
b = 0
for i in xrange(1, n):
    a = max(a, dfs(i, 1))
print a
0