結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー |
![]() |
提出日時 | 2018-04-04 16:58:12 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 84 ms / 5,000 ms |
コード長 | 1,921 bytes |
コンパイル時間 | 1,368 ms |
コンパイル使用メモリ | 159,380 KB |
実行使用メモリ | 74,240 KB |
最終ジャッジ日時 | 2024-06-26 08:51:15 |
合計ジャッジ時間 | 4,786 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define INF 1.1e9#define LINF 1.1e18#define FOR(i,a,b) for (int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)#define ALL(v) (v).begin(),(v).end()#define pb push_back#define pf push_front#define fi first#define se second#define BIT(x,n) bitset<n>(x)#define PI 3.14159265358979323846typedef long long ll;typedef pair<int,int> P;typedef pair<ll,P> PP;//-----------------------------------------------------------------------------int n,m,w[3010];int dp[3010][3010][2]; //頂点iまででj個の頂点を使ったときの最大値。kは頂点iを使ったかどうか。int ans=-INF;int main() {cin.tie(0);ios::sync_with_stdio(false);REP(i,3010) FOR(j,0,3010) dp[i][j][0]=dp[i][j][1]=-INF;cin>>n>>m;REP(i,n) cin>>w[i+1];// 頂点1を使わないdp[1][0][0]=0;FOR(i,1,n+1) {FOR(j,0,3001) {// 頂点i+1を使うdp[i+1][j+1][1]=max(dp[i+1][j+1][1],max(dp[i][j][0],dp[i][j][1]+w[i]));// 頂点i+1を使わないdp[i+1][j][0]=max(dp[i+1][j][0],max(dp[i][j][0],dp[i][j][1]));}ans=max(ans,dp[i][m][0]);}ans=max(ans,dp[n+1][m][0]);/*FOR(i,1,n+2) {REP(j,n+1) cout<<(dp[i][j][0]>=0?dp[i][j][0]:-1)<<' ';cout<<'|';REP(j,n+1) cout<<(dp[i][j][1]>=0?dp[i][j][1]:-1)<<' ';cout<<endl;}cout<<endl;*/REP(i,3010) FOR(j,0,3010) dp[i][j][0]=dp[i][j][1]=-INF;// 頂点1を使う。dp[1][1][1]=0;FOR(i,1,n+1) {FOR(j,1,3001) {// 頂点iを使うdp[i+1][j+1][1]=max(dp[i+1][j+1][1],max(dp[i][j][0],dp[i][j][1]+w[i]));// 頂点iを使わないdp[i+1][j][0]=max(dp[i+1][j][0],max(dp[i][j][0],dp[i][j][1]));}if(i==n) ans=max(ans,dp[n][m][1]+w[n]);else ans=max(ans,dp[i][m][1]);}/*FOR(i,1,n+2) {REP(j,n+1) cout<<(dp[i][j][0]>=0?dp[i][j][0]:-1)<<' ';cout<<'|';REP(j,n+1) cout<<(dp[i][j][1]>=0?dp[i][j][1]:-1)<<' ';cout<<endl;}*/cout<<ans<<endl;return 0;}