結果
問題 |
No.324 落ちてた閉路グラフ
|
ユーザー |
![]() |
提出日時 | 2015-12-17 01:17:37 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,022 bytes |
コンパイル時間 | 779 ms |
コンパイル使用メモリ | 73,576 KB |
実行使用メモリ | 34,176 KB |
最終ジャッジ日時 | 2024-09-16 06:44:24 |
合計ジャッジ時間 | 7,207 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | TLE * 1 -- * 33 |
ソースコード
#include<iostream> #include<string> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include<functional> #include<cstdio> #include<cstdlib> #include<cmath> using namespace std; #define mind(a,b) (a>b?b:a) #define maxd(a,b) (a>b?a:b) #define absd(x) (x<0?-(x):x) #define pow2(x) ((x)*(x)) #define rep(i,n) for(int i=0; i<n; ++i) #define repr(i,n) for(int i=n-1; i>=0; --i) #define repl(i,s,n) for(int i=s; i<=n; ++i) #define replr(i,s,n) for(int i=n; i>=s; --i) #define repf(i,s,n,j) for(int i=s; i<=n; i+=j) #define repe(e,obj) for(auto e : obj) #define SP << " " << #define COL << " : " << #define COM << ", " << #define ARR << " -> " << #define PNT(STR) cout << STR << endl #define POS(X,Y) "(" << X << ", " << Y << ")" #define DEB(A) " (" << #A << ") " << A #define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl #define ALL(V) (V).begin(), (V).end() #define INF 1000000007 #define INFLL 10000000000000000007LL #define EPS 1e-9 typedef unsigned int uint; typedef unsigned long ulong; typedef unsigned long long ull; typedef long long ll; typedef long double ld; typedef pair<int, int> P; //typedef pair<ll, ll> P; typedef pair<P, int> PI; typedef pair<int, P> IP; typedef pair<P, P> PP; typedef priority_queue<P, vector<P>, greater<P> > pvqueue; #define N 3003 int n, m; int w[N]; int dp[N][N]; int base; int dfs(int c, int s) { if(s==m) return (c==n-1 ? base : 0); if(c >= n) return -INF; if(dp[c][s]!=-INF) return dp[c][s]; int ret = dfs(c+1, s+1) + w[c]; repl(i, c+2, n-1) { int r = dfs(i, s+1); ret = maxd(ret, r); } return dp[c][s] = ret; } int main() { cin >> n >> m; rep(i, n) cin >> w[i]; rep(i, n) rep(j, m+1) dp[i][j] = -INF; base = w[n-1]; int ans = w[0] + dfs(1, 2); repl(i, 2, n-1) { int r = dfs(i, 2); ans = maxd(ans, r); } rep(i, n) rep(j, m+1) dp[i][j] = -INF; base = 0; repl(i, 1, n-1) { int r = dfs(i, 1); ans = maxd(ans, r); } cout << ans << endl; return 0; }