結果
問題 | No.324 落ちてた閉路グラフ |
ユーザー | nanophoto12 |
提出日時 | 2015-12-27 22:34:18 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 275 ms / 5,000 ms |
コード長 | 1,945 bytes |
コンパイル時間 | 618 ms |
コンパイル使用メモリ | 69,916 KB |
実行使用メモリ | 394,104 KB |
最終ジャッジ日時 | 2024-04-27 16:07:28 |
合計ジャッジ時間 | 11,092 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 237 ms
393,972 KB |
testcase_01 | AC | 245 ms
394,072 KB |
testcase_02 | AC | 236 ms
393,956 KB |
testcase_03 | AC | 244 ms
393,960 KB |
testcase_04 | AC | 254 ms
394,100 KB |
testcase_05 | AC | 272 ms
394,088 KB |
testcase_06 | AC | 259 ms
393,936 KB |
testcase_07 | AC | 275 ms
394,044 KB |
testcase_08 | AC | 250 ms
394,104 KB |
testcase_09 | AC | 253 ms
393,900 KB |
testcase_10 | AC | 244 ms
393,948 KB |
testcase_11 | AC | 251 ms
393,992 KB |
testcase_12 | AC | 227 ms
394,096 KB |
testcase_13 | AC | 242 ms
393,924 KB |
testcase_14 | AC | 229 ms
393,940 KB |
testcase_15 | AC | 257 ms
393,960 KB |
testcase_16 | AC | 230 ms
394,072 KB |
testcase_17 | AC | 232 ms
393,976 KB |
testcase_18 | AC | 231 ms
394,068 KB |
testcase_19 | AC | 238 ms
393,964 KB |
testcase_20 | AC | 241 ms
394,008 KB |
testcase_21 | AC | 232 ms
393,928 KB |
testcase_22 | AC | 231 ms
393,980 KB |
testcase_23 | AC | 232 ms
393,800 KB |
testcase_24 | AC | 232 ms
393,972 KB |
testcase_25 | AC | 229 ms
394,104 KB |
testcase_26 | AC | 234 ms
393,956 KB |
testcase_27 | AC | 229 ms
393,936 KB |
testcase_28 | AC | 233 ms
393,924 KB |
testcase_29 | AC | 230 ms
394,004 KB |
testcase_30 | AC | 230 ms
394,012 KB |
testcase_31 | AC | 229 ms
393,800 KB |
testcase_32 | AC | 261 ms
394,092 KB |
testcase_33 | AC | 251 ms
393,968 KB |
testcase_34 | AC | 246 ms
394,036 KB |
testcase_35 | AC | 230 ms
393,824 KB |
testcase_36 | AC | 233 ms
394,028 KB |
testcase_37 | AC | 228 ms
394,040 KB |
ソースコード
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <cmath> using namespace std; #define FOR(x,y) for(int x = 0;x < y;x++) #define LLI long long int template<int um> class UF { public: vector<int> par,rank,cnt; UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;} void reinit() {FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;} int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));} int count(int x) { return cnt[operator[](x)];} int operator()(int x,int y) { if((x=operator[](x))==(y=operator[](y))) return x; cnt[y]=cnt[x]=cnt[x]+cnt[y]; if(rank[x]>rank[y]) return par[x]=y; rank[x]+=rank[x]==rank[y]; return par[y]=x; } }; int dp[2][2][5000][5000]; int w[5000]; const int minimum = -100000000; int main() { int n, m; cin >> n >> m; FOR(i, n) { cin >> w[i]; } int* pointer = &dp[0][0][0][0]; FOR(i, 2 * 2 * 5000 * 5000) { pointer[i] = minimum; } dp[0][0][0][0] = 0; dp[1][1][0][1] = 0; int maxValue = minimum; FOR(u ,2) { FOR(i, n-1) { FOR(j,m + 1) { dp[u][0][i+1][j] = max(dp[u][0][i][j], dp[u][1][i][j]); //cout << "not used" << dp[u][0][i+1][j] << endl; if(j > 0) { dp[u][1][i+1][j] = max(dp[u][0][i][j-1], dp[u][1][i][j-1] + w[i]); //cout << "used" << dp[u][1][i+1][j] << endl; } } } maxValue = max(maxValue, dp[u][0][n-1][m]); if(u == 0) { maxValue = max(maxValue, dp[u][1][n-1][m]); } else if(u == 1) { maxValue = max(maxValue, dp[u][1][n-1][m] + w[n-1]); } //cout << "max " << maxValue << endl; } cout << maxValue << endl; return 0; }