結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2016-01-25 23:24:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 107 ms / 5,000 ms |
コード長 | 2,077 bytes |
コンパイル時間 | 1,000 ms |
コンパイル使用メモリ | 90,952 KB |
実行使用メモリ | 144,256 KB |
最終ジャッジ日時 | 2024-11-15 19:40:15 |
合計ジャッジ時間 | 2,763 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cstdlib>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <ctime>#include <fstream>#include <queue>#include <complex>#define INF 100000000#define YJ 1145141919#define INF_INT_MAX 2147483647#define INF_LL_MAX 9223372036854775807#define EPS 1e-10#define Pi acos(-1)#define LL long long#define ULL unsigned long long#define LD long doubleusing namespace std;#define MAX_N 3005int N, M;int W[MAX_N];int dp[MAX_N][MAX_N][2][2];void Init(){for(int i = 0; i <= N; i++){for(int j = 0; j <= M; j++){for(int k = 0; k < 2; k++){for(int l = 0; l < 2; l++){dp[i][j][k][l] = -INF;}}}}}int main(){cin >> N >> M;for(int i = 0; i < N; i++){cin >> W[i];}Init();dp[0][0][0][0] = 0;for(int i = 0; i < N; i++){for(int j = M; j >= 0; j--){//最初if(i == 0){dp[i+1][j][0][0] = max(dp[i+1][j][0][0], dp[i][j][0][0]);if(j < M)dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1], dp[i][j][0][0]);}//途中else{//今見ている座標の頂点を選択しないdp[i+1][j][0][0] = max(dp[i+1][j][0][0],max(dp[i][j][1][0], dp[i][j][0][0]));dp[i+1][j][0][1] = max(dp[i+1][j][0][1],max(dp[i][j][1][1], dp[i][j][0][1]));//今見ている頂点を選択するif(j < M){dp[i+1][j+1][1][0] = max(dp[i+1][j+1][1][0],max(dp[i][j][1][0] + W[i-1], dp[i][j][0][0]));dp[i+1][j+1][1][1] = max(dp[i+1][j+1][1][1],max(dp[i][j][1][1] + W[i-1], dp[i][j][0][1]));}}}}dp[N][M][1][1] += W[N-1];int ans = -INF;for(int i = 0; i < 2; i++){for(int j = 0; j < 2; j++){ans = max(ans, dp[N][M][i][j]);}}cout << ans << endl;return 0;}