結果
問題 | No.1542 ぽんぽんぽん ぽんぽんぽんぽん ぽんぽんぽん |
ユーザー | tails |
提出日時 | 2022-10-20 16:29:17 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,459 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 170,360 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-06-30 08:55:59 |
合計ジャッジ時間 | 3,295 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 3 ms
6,948 KB |
testcase_06 | AC | 7 ms
6,940 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 13 ms
6,944 KB |
testcase_09 | AC | 4 ms
6,944 KB |
testcase_10 | AC | 14 ms
6,940 KB |
testcase_11 | AC | 12 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 3 ms
6,940 KB |
testcase_14 | AC | 7 ms
6,940 KB |
testcase_15 | AC | 2 ms
6,940 KB |
testcase_16 | AC | 6 ms
6,940 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 2 ms
6,944 KB |
testcase_20 | AC | 13 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 7 ms
6,940 KB |
testcase_23 | AC | 13 ms
6,944 KB |
testcase_24 | AC | 14 ms
6,944 KB |
testcase_25 | AC | 13 ms
6,944 KB |
testcase_26 | AC | 14 ms
6,940 KB |
testcase_27 | AC | 16 ms
6,944 KB |
testcase_28 | AC | 16 ms
6,944 KB |
testcase_29 | AC | 13 ms
6,940 KB |
testcase_30 | AC | 15 ms
6,944 KB |
testcase_31 | AC | 13 ms
6,940 KB |
testcase_32 | AC | 15 ms
6,940 KB |
ソースコード
// original code https://yukicoder.me/submissions/666144 by vkgainz // hayaku naruka na? #include <bits/stdc++.h> using namespace std; int dp[505][505]; int main() { int N; cin >> N; string S; cin >> S; #if 1 // added by tails { string T; T.reserve(N); for(char c:S){ int l=T.size(); if(c=='o'&&l>=1&&T[l-1]==c){ continue; } if(c=='n'){ if(l>=2&&T[l-2]=='p'&&T[l-1]=='o'){ T.resize(l-=2); dp[l+1][l+1]+=1; c='x'; } else if(l>=3&&T[l-3]=='p'&&T[l-2]+T[l-1]=='o'+'x'){ T.resize(l-=3); dp[l+1][l+1]=dp[l+2][l+2]+dp[l+3][l+3]+1; dp[l+2][l+2]=0; dp[l+3][l+3]=0; c='x'; } } T+=c; } S=T; N=S.size(); } #endif for(int len = 2; len <= N; len++) { for(int i = 1; i + len - 1 <= N; i++) { int j = i + len - 1; dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]); if(S[i - 1] == 'p' && S[j - 1] == 'n') { for(int k = i + 1; k < j; k++) if(S[k - 1] == 'o') dp[i][j] = max(dp[i][j], 1 + dp[i + 1][k - 1] + dp[k + 1][j - 1]); } for(int k = i; k <= j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]); } } } int ans = -1; for(int i = 1; i <= N; i++) { if(dp[1][i] >= 1 && dp[i + 1][N] >= 1) ans = max(ans, dp[1][i] + dp[i + 1][N] - 2); } cout << ans << "\n"; }