QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408844#8554. Bot Friendsdaduoli#WA 71ms6012kbC++231.2kb2024-05-11 09:03:052024-05-11 09:03:05

Judging History

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

  • [2024-05-11 09:03:05]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:6012kb
  • [2024-05-11 09:03:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int read(){
	char ch=getchar();
	while(!isdigit(ch) && ch!='-') ch=getchar();
	int x=0,ff=1; if(ch=='-') ff=-1,ch=getchar();
	while(isdigit(ch)) x=(x<<3) + (x<<1) + (ch^48),ch=getchar();
	return x*ff;
}
const int N=5e3+5,inf=1e9;
char ch[N]; int n,f[N][N][2],F[N],G[N];
void vmain(){
	scanf("%s",ch+1); n=strlen(ch+1);
	for(int i=1;i<=n;i++){
		f[i][i][0]=f[i][i][1]=-inf; F[i]=G[i]=0;
		if(ch[i]!='>') f[i][i][0]=0;
		if(ch[i]!='<') f[i][i][1]=0;
	}
	for(int len=2;len<=n;len++)
		for(int l=1,r=len;r<=n;l++,r++){
			f[l][r][0]=f[l][r][1]=-inf;
			if(ch[l]!='>') f[l][r][0]=max(f[l][r][0],f[l+1][r][0]);
			if(ch[r]!='>') f[l][r][0]=max({f[l][r][0],f[l][r-1][0],f[l][r-1][1]+1});
			if(ch[r]!='<') f[l][r][1]=max(f[l][r][1],f[l][r-1][1]);
			if(ch[l]!='<') f[l][r][1]=max({f[l][r][1],f[l+1][r][1],f[l+1][r][0]+1});
		}
	F[0]=0; for(int i=1;i<=n;i++) for(int j=i;j>=1;j--) F[i]=max(F[i],F[j-1]+f[j][i][0]);
	G[n+1]=0; for(int i=n;i>=1;i--) for(int j=i;j<=n;j++) G[i]=max(G[i],G[j+1]+f[i][j][1]);
	int ans=0;
	for(int i=0;i<=n;i++) ans=max(ans,F[i]+G[i+1]);
	printf("%d\n",ans);
}
int main(){
	int T=read(); while(T--) vmain();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 71ms
memory: 3860kb

input:

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

output:

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

result:

wrong answer 30th numbers differ - expected: '6', found: '5'