結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
|
提出日時 | 2017-04-13 19:07:56 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 130 ms / 5,000 ms |
コード長 | 935 bytes |
コンパイル時間 | 1,414 ms |
コンパイル使用メモリ | 159,464 KB |
実行使用メモリ | 144,536 KB |
最終ジャッジ日時 | 2024-07-18 12:57:16 |
合計ジャッジ時間 | 3,142 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define REP(i,n) for (int i=0;i<(n);i++)#define REP2(i,m,n) for (int i=m;i<(n);i++)const int INF = 1 << 29;int N, M;int W[3010];int dp[3010][3010][2][2];int main() {cin >> N >> M;REP(i, N) cin >> W[i];if (M == 0) {cout << 0 << endl;return 0;}REP(i, N+1) REP(j, M+1) REP(k, 2) REP(l, 2) dp[i][j][k][l] = -INF;dp[0][0][0][0] = 0;dp[0][1][1][1] = 0;REP2(i, 1, N) REP(j, M+1) REP(k, 2) REP(l, 2) {if (dp[i-1][j][k][l] == -INF) continue;int take = 0;if (k) take += W[i-1];if (i == N-1 && l) take += W[N-1];if (j < M) dp[i][j+1][1][l] =max(dp[i][j+1][1][l], dp[i-1][j][k][l] + take);dp[i][j][0][l] = max(dp[i][j][0][l], dp[i-1][j][k][l]);}int ans = -INF;REP(k, 2) REP(l, 2) ans = max(ans, dp[N-1][M][k][l]);cout << ans << endl;}