結果
問題 |
No.324 落ちてた閉路グラフ
|
ユーザー |
|
提出日時 | 2017-06-27 17:15:47 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2,105 ms / 5,000 ms |
コード長 | 1,125 bytes |
コンパイル時間 | 910 ms |
コンパイル使用メモリ | 101,184 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-12 20:34:29 |
合計ジャッジ時間 | 15,221 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string; void main() { auto rd = readln.split.to!(int[]), n = rd[0], m = rd[1]; auto w = readln.split.to!(int[]); auto dpInit() { auto dp = new int[][](m+1, 2); foreach (j; 0..m+1) foreach (k; 0..2) dp[j][k] = -10^^9; return dp; } auto calc1() { auto dp = dpInit(); dp[0][0] = 0; foreach (i; 1..n) { auto dp2 = dpInit(); foreach (j; 0..m+1) { dp2[j][0] = max(dp2[j][0], dp[j][0], dp[j][1]); if (j < m) dp2[j+1][1] = max(dp2[j+1][1], dp[j][0], dp[j][1] + w[i-1]); } dp = dp2; } return max(dp[m][0], dp[m][1]); } auto calc2() { auto dp = dpInit(); dp[1][1] = 0; foreach (i; 1..n) { auto dp2 = dpInit(); foreach (j; 0..m+1) { dp2[j][0] = max(dp2[j][0], dp[j][0], dp[j][1]); if (j < m) dp2[j+1][1] = max(dp2[j+1][1], dp[j][0], dp[j][1] + w[i-1]); } dp = dp2; } return max(dp[m][0], dp[m][1] + w[n-1]); } if (m == 0) writeln(0); else writeln(max(calc1, calc2)); }