QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#456266#8554. Bot Friendskkkgjyismine4WA 102ms8088kbC++231.5kb2024-06-27 16:42:222024-06-27 16:42:23

Judging History

你现在查看的是最新测评结果

  • [2024-06-27 16:42:23]
  • 评测
  • 测评结果:WA
  • 用时:102ms
  • 内存:8088kb
  • [2024-06-27 16:42:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n;char s[5050];
int f[5050][5050][2][2],g[5050][5050][2][2];
void upd(int &x,const int y){x=((x>y)?x:y);}
void solve(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=0;i<=n+1;++i)for(int j=0;j<=n+1;++j)for(int a=0;a<2;++a)for(int b=0;b<2;++b)f[i][j][a][b]=g[i][j][a][b]=-inf;
	f[0][0][0][0]=g[n+1][0][0][0]=0;
	for(int i=1;i<=n;++i)
	  for(int j=0;j<i;++j)
	    for(int k=0;k<2;++k)
	       for(int o=0;o<2;++o)
	        if(f[i-1][j][k][o]>=0){
	         	if(s[i]!='<')upd(f[i][j+1][1][0],f[i-1][j][k][o]+1);
				if(s[i]!='>'){
					if(!j)upd(f[i][0][0][0],f[i-1][j][k][o]+k);
					else{
						if(i==1||o)upd(f[i][j-1][1][1],f[i-1][j][k][o]+1);
						else upd(f[i][j-1][1][1],f[i-1][j][k][o]);
					}
				}
			}
	for(int i=n;i>=1;--i)
	  for(int j=0;j<n-i+1;++j)
	    for(int k=0;k<2;++k)
	       for(int o=0;o<2;++o)
	        if(g[i+1][j][k][o]>=0){
	         	if(s[i]!='>')upd(g[i][j+1][1][0],g[i+1][j][k][o]+1);
				if(s[i]!='<'){
					if(!j)upd(g[i][0][0][0],g[i+1][j][k][o]+k);
					else{
						if(i==1||o)upd(g[i][j-1][1][1],g[i+1][j][k][o]+1);
						else upd(g[i][j-1][1][1],g[i+1][j][k][o]);
					}
				}
			}
	int ans=0;
	for(int i=0;i<=n;++i)
	  for(int a=0;a<2;++a)
	    for(int b=0;b<2;++b)
	      for(int c=0;c<2;++c)
	        for(int d=0;d<2;++d)upd(ans,f[i][0][a][b]+g[i+1][0][c][d]);
	printf("%d\n",ans);
}
int main(){
	int T;cin>>T;
	while(T--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 8088kb

input:

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 102ms
memory: 8040kb

input:

100000
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
>><>><<<<<
>?>?>?<<>>
?><?<<?<><
???><>?>?>
<??>?<<><?
??>><?<>>>
<><><?<>>?
?>>?>???><
?<?><?<<>?
>>><?<??><
><><<>?>?<
>?><>><<<?
>??>?><?<>
?????<><?>
<><<?<<>?<
><?>>?>?>?
?><><<<>>?
?<>?<>?<<<
<><<<<<>>>
?>?>?><<>>
<>?<>><>?<
<<<?<>>...

output:

8
7
8
5
6
7
7
6
6
7
6
5
7
7
8
7
8
8
7
6
6
7
8
2
6
6
3
9
6
5
5
8
5
8
7
6
8
7
7
6
6
7
4
2
7
5
7
7
9
6
7
5
7
8
8
8
8
7
5
6
7
8
7
8
7
5
8
6
7
9
7
7
6
9
5
8
6
6
5
5
7
8
5
3
8
6
5
8
5
7
5
7
7
8
3
8
9
7
8
7
7
4
8
8
7
5
9
6
8
7
8
7
5
7
8
5
7
6
6
8
8
7
7
8
6
7
8
6
6
8
7
8
7
6
5
5
7
8
6
8
6
7
5
7
4
6
6
7
7
8
...

result:

wrong answer 6th numbers differ - expected: '8', found: '7'