結果
問題 | No.291 黒い文字列 |
ユーザー | chocorusk |
提出日時 | 2019-01-12 11:48:22 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,743 bytes |
コンパイル時間 | 819 ms |
コンパイル使用メモリ | 99,436 KB |
実行使用メモリ | 39,168 KB |
最終ジャッジ日時 | 2024-05-09 20:55:07 |
合計ジャッジ時間 | 8,611 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
39,040 KB |
testcase_01 | AC | 34 ms
39,040 KB |
testcase_02 | AC | 34 ms
39,040 KB |
testcase_03 | AC | 33 ms
38,912 KB |
testcase_04 | AC | 33 ms
39,040 KB |
testcase_05 | AC | 34 ms
38,912 KB |
testcase_06 | WA | - |
testcase_07 | AC | 35 ms
38,912 KB |
testcase_08 | AC | 35 ms
39,040 KB |
testcase_09 | AC | 35 ms
39,040 KB |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 33 ms
38,912 KB |
testcase_15 | AC | 32 ms
38,784 KB |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | AC | 379 ms
38,912 KB |
testcase_26 | AC | 395 ms
39,040 KB |
testcase_27 | AC | 389 ms
38,912 KB |
testcase_28 | AC | 383 ms
39,040 KB |
testcase_29 | WA | - |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #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> #include <cassert> using namespace std; typedef long long int ll; typedef pair<int, int> P; int main() { int dp[2][101][51][34][26]={}; string s; cin>>s; int n=s.size(); for(int i=0; i<n; i++){ for(int j=0; j<=i; j++){ for(int k=0; k<=i/2; k++){ for(int l=0; l<=i/3; l++){ for(int m=0; m<=i/4; m++){ dp[(i&1)^1][j][k][l][m]=dp[i&1][j][k][l][m]; } } } } for(int j=0; j<=i; j++){ for(int k=0; k<=i/2; k++){ for(int l=0; l<=i/3; l++){ for(int m=0; m<=i/4; m++){ if(s[i]=='K' || s[i]=='?'){ dp[(i&1)^1][j+1][k][l][m]=max(dp[i&1][j][k][l][m], dp[(i&1)^1][j+1][k][l][m]); } if((s[i]=='U' || s[i]=='?') && j>0){ dp[(i&1)^1][j-1][k+1][l][m]=max(dp[i&1][j][k][l][m], dp[(i&1)^1][j-1][k+1][l][m]); } if((s[i]=='R' || s[i]=='?') && k>0){ dp[(i&1)^1][j][k-1][l+1][m]=max(dp[i&1][j][k][l][m], dp[(i&1)^1][j][k-1][l+1][m]); } if((s[i]=='O' || s[i]=='?') && l>0){ dp[(i&1)^1][j][k][l-1][m+1]=max(dp[i&1][j][k][l][m], dp[(i&1)^1][j][k][l-1][m+1]); } if((s[i]=='I' || s[i]=='?') && m>0){ dp[(i&1)^1][j][k][l][m-1]=max(dp[i&1][j][k][l][m]+1, dp[(i&1)^1][j][k][l][m-1]); } } } } } } int ans=0; for(int j=0; j<=n; j++){ for(int k=0; k<=n/2; k++){ for(int l=0; l<=n/3; l++){ for(int m=0; m<=n/4; m++){ ans=max(ans, dp[n&1][j][k][l][m]); } } } } cout<<ans<<endl; return 0; }