結果
問題 | 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; }