結果
問題 |
No.324 落ちてた閉路グラフ
|
ユーザー |
|
提出日時 | 2016-02-29 11:58:51 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 534 ms / 5,000 ms |
コード長 | 1,135 bytes |
コンパイル時間 | 1,150 ms |
コンパイル使用メモリ | 67,872 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-15 19:40:30 |
合計ジャッジ時間 | 4,889 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <iostream> #include <vector> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; } using namespace std; const int INF = 1e9; int main() { int n, m; cin >> n >> m; vector<int> w(n); repeat (i,n) cin >> w[i]; int ans = - INF; repeat (p,2) { vector<vector<int> > prv; vector<vector<int> > cur(max(2, m+1), vector<int>(2, - INF)); auto fly = [&]() { cur.swap(prv); cur.clear(); cur.resize(m+1, vector<int>(2, - INF)); }; cur[p][p] = 0; repeat (i,n-1) { fly(); repeat (j,m+1) { ;;;;;;;;;;; cur[j][false] = max(prv[j ][false], prv[j ][true]); if (j >= 1) cur[j][ true] = max(prv[j-1][false], prv[j-1][true] + w[i]); } } fly(); repeat (j,m+1) { cur[j][false] = max(prv[j][false], prv[j][true]); cur[j][ true] = max(prv[j][false], prv[j][true] + (p ? w[n-1] : 0)); } setmax(ans, cur[m][p]); } cout << ans << endl; return 0; }