結果
問題 | No.291 黒い文字列 |
ユーザー |
![]() |
提出日時 | 2015-10-16 22:36:01 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 817 ms / 2,000 ms |
コード長 | 1,558 bytes |
コンパイル時間 | 1,521 ms |
コンパイル使用メモリ | 162,524 KB |
実行使用メモリ | 35,420 KB |
最終ジャッジ日時 | 2024-07-21 19:18:44 |
合計ジャッジ時間 | 14,414 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef signed long long ll;#undef _P#define _P(...) (void)printf(__VA_ARGS__)#define FOR(x,to) for(x=0;x<to;x++)#define FORR(x,arr) for(auto& x:arr)#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)#define ALL(a) (a.begin()),(a.end())#define ZERO(a) memset(a,0,sizeof(a))#define MINUS(a) memset(a,0xff,sizeof(a))//-------------------------------------------------------int L;string S;int dp[2][21][21][21][21][21];void solve() {int i,j,k,l,r,x,y; string s;int a,b,c,d,e;cin>>S;L=S.size();ZERO(dp);int ma=0;dp[0][0][0][0][0][0]=1;FOR(i,L) {int cur=i%2,tar=cur^1;ZERO(dp[tar]);for(a=19;a>=0;a--)for(b=20;b>=0;b--)for(c=20;c>=0;c--)for(d=20;d>=0;d--)for(e=20;e>=0;e--) if(dp[cur][a][b][c][d][e]) {dp[tar][a][b][c][d][e]=dp[cur][a][b][c][d][e];if(S[i]=='K' || S[i]=='?') {if(e<20) dp[tar][a][b][c][d][e+1] = 1;}if(S[i]=='U' || S[i]=='?') {if(d<20 && e) dp[tar][a][b][c][d+1][e-1] = 1;}if(S[i]=='R' || S[i]=='?') {if(c<20 && d) dp[tar][a][b][c+1][d-1][e] = 1;}if(S[i]=='O' || S[i]=='?') {if(b<20 && c) dp[tar][a][b+1][c-1][d][e] = 1;}if(S[i]=='I' || S[i]=='?') {if(a<20 && b) {dp[tar][a+1][b-1][c][d][e] = 1;ma=max(ma,a+1);}}}}cout<<ma<<endl;}int main(int argc,char** argv){string s;int i;if(argc==1) ios::sync_with_stdio(false);FOR(i,argc-1) s+=argv[i+1],s+='\n';FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);solve(); return 0;}