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