結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー | koyumeishi |
提出日時 | 2015-12-17 11:22:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,471 bytes |
コンパイル時間 | 464 ms |
コンパイル使用メモリ | 68,260 KB |
最終ジャッジ日時 | 2024-11-14 19:31:18 |
合計ジャッジ時間 | 814 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:31:32: error: ‘accumulate’ was not declared in this scope 31 | printf("%d\n", accumulate(w, w+n, 0)); | ^~~~~~~~~~ main.cpp:20:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 20 | scanf("%d%d", &n,&m); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:24:37: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 24 | for(int i=0; i<n; i++) scanf("%d", &w[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include <iostream> #include <vector> #include <cstdio> #include <sstream> #include <map> #include <string> #include <algorithm> #include <queue> #include <cmath> #include <set> using namespace std; int dp [4][3002]; int dp_[4][3002]; int w[3002]; int main(){ int n,m; //cin >> n >> m; scanf("%d%d", &n,&m); //vector<int> w(n); //cin >> w; //for(int& x:w) scanf("%d", &x); for(int i=0; i<n; i++) scanf("%d", &w[i]); if(m<=1){ cout << 0 << endl; return 0; } if(n==m){ printf("%d\n", accumulate(w, w+n, 0)); return 0; } const int inf = 100000000; for(int i=0; i<4; i++){ fill(dp[i], dp[i]+m+2, -inf); fill(dp_[i], dp_[i]+m+2, -inf); } //vector<vector<vector<int>>> dp (2,vector<vector<int>>(2,vector<int>(m+2, -inf))); //vector<vector<vector<int>>> dp_(2,vector<vector<int>>(2,vector<int>(m+2, -inf))); dp[0b00][0] = 0; dp[0b11][1] = 0; for(int i=1; i<n; i++){ for(int k=max(0,m-(n-i)); k<=min(i,m); ++k){ dp_[0b00][k] = max({dp_[0b00][k], dp[0b00][k], dp[0b01][k]}); dp_[0b01][k+1] = max({dp_[0b01][k+1], dp[0b00][k], dp[0b01][k]+w[i-1]}); dp_[0b10][k] = max({dp_[0b10][k], dp[0b10][k], dp[0b11][k]}); dp_[0b11][k+1] = max({dp_[0b11][k+1], dp[0b10][k], dp[0b11][k]+w[i-1]}); dp[0b00][k] = dp[0b01][k] = dp[0b10][k] = dp[0b11][k] = -inf; } swap(dp, dp_); } int ans = max({dp[0b00][m], dp[0b01][m], dp[0b10][m], dp[0b11][m]+w[n-1]}); printf("%d\n", ans); //cout << ans << endl; return 0; }