結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2015-12-17 10:53:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 65 ms / 5,000 ms |
コード長 | 1,198 bytes |
コンパイル時間 | 981 ms |
コンパイル使用メモリ | 82,924 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-15 19:30:03 |
合計ジャッジ時間 | 2,561 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>#include <set>using namespace std;template<class T> istream& operator >> (istream& is, vector<T>& vec){ for(T& val: vec) is >> val; return is;}int main(){int n,m;cin >> n >> m;vector<int> w(n);cin >> w;if(m==0){cout << 0 << endl;return 0;}const int inf = 100000000;vector<vector<vector<int>>> dp (2,vector<vector<int>>(2,vector<int>(m+1, -inf)));dp[0][0][0] = 0;dp[1][1][1] = 0;for(int i=1; i<n; i++){vector<vector<vector<int>>> dp_(2,vector<vector<int>>(2,vector<int>(m+1, -inf)));for(int start=0; start<2; start++)for(int last=0; last<2; last++)for(int k=0; k<=min(i,m); k++){if(dp[start][last][k] <= -inf) continue;dp_[start][0][k] = max(dp_[start][0][k], dp[start][last][k]);if(k+1<=m){int next = dp[start][last][k];if(last){next += w[i-1];}dp_[start][1][k+1] = max(dp_[start][1][k+1], next);}}swap(dp, dp_);}int ans = max({dp[0][0][m], dp[0][1][m], dp[1][0][m], dp[1][1][m]+w[n-1]});cout << ans << endl;return 0;}