結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2018-12-09 22:56:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 117 ms / 5,000 ms |
コード長 | 1,565 bytes |
コンパイル時間 | 1,040 ms |
コンパイル使用メモリ | 97,144 KB |
実行使用メモリ | 73,856 KB |
最終ジャッジ日時 | 2024-09-16 15:38:25 |
合計ジャッジ時間 | 4,951 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <cstdio>#include <cstring>#include <string>#include <iostream>#include <cmath>#include <bitset>#include <vector>#include <map>#include <set>#include <queue>#include <deque>#include <algorithm>#include <complex>#include <unordered_map>#include <unordered_set>#include <random>using namespace std;typedef long long int ll;typedef pair<int, int> P;const int INF=1e9;int main(){int n, m;cin>>n>>m;int w[3001];for(int i=0; i<n; i++) cin>>w[i];int dp[2][3001][3001];for(int i=0; i<n; i++){for(int j=0; j<=m; j++){dp[0][i][j]=dp[1][i][j]=-INF;}}dp[1][0][1]=0;for(int i=0; i<n-1; i++){for(int j=0; j<=m; j++){if(dp[0][i][j]>-INF){dp[0][i+1][j]=max(dp[0][i][j], dp[0][i+1][j]);if(j+1<=m) dp[1][i+1][j+1]=max(dp[0][i][j], dp[1][i+1][j+1]);}if(dp[1][i][j]>-INF){dp[0][i+1][j]=max(dp[1][i][j], dp[0][i+1][j]);if(j+1<=m) dp[1][i+1][j+1]=max(dp[1][i][j]+w[i], dp[1][i+1][j+1]);}}}int ans=max(dp[0][n-1][m], dp[1][n-1][m]+w[n-1]);for(int i=0; i<n; i++){for(int j=0; j<=m; j++){dp[0][i][j]=dp[1][i][j]=-INF;}}dp[0][0][0]=0;for(int i=0; i<n-1; i++){for(int j=0; j<=m; j++){if(dp[0][i][j]>-INF){dp[0][i+1][j]=max(dp[0][i][j], dp[0][i+1][j]);if(j+1<=m) dp[1][i+1][j+1]=max(dp[0][i][j], dp[1][i+1][j+1]);}if(dp[1][i][j]>-INF){dp[0][i+1][j]=max(dp[1][i][j], dp[0][i+1][j]);if(j+1<=m) dp[1][i+1][j+1]=max(dp[1][i][j]+w[i], dp[1][i+1][j+1]);}}}ans=max({ans, dp[0][n-1][m], dp[1][n-1][m]});cout<<ans<<endl;return 0;}