QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408837#8554. Bot Friendsdaduoli#WA 47ms3932kbC++23987b2024-05-11 08:42:422024-05-11 08:42:43

Judging History

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

  • [2024-05-11 08:42:43]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:3932kb
  • [2024-05-11 08:42:42]
  • 提交

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][2];
void vmain(){
	scanf("%s",ch+1); n=strlen(ch+1);
	for(int len=2;len<=n;len++)
		for(int l=1,r=len;r<=n;l++,r++){
			f[l][r][0]=max(f[l][r-1][0],f[l+1][r][0]); f[l][r][1]=max(f[l][r-1][1],f[l+1][r][1]);
			if(ch[l]!='<') f[l][r][1]=max(f[l][r][1],f[l+1][r][0]+1);
			if(ch[r]!='>') f[l][r][0]=max(f[l][r][0],f[l][r-1][1]+1);	
		}
	for(int i=1;i<=n;i++){
		F[i][0]=F[i][1]=0;
		for(int j=i-1;j>=1;j--) {
			F[i][0]=max(F[i][0],F[j-1][0]+f[j][i][0]);
			F[i][1]=max(F[i][1],max(F[j-1][0],F[j-1][1])+f[j][i][1]);
		}
	} printf("%d\n",max(F[n][0],F[n][1]));
}
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: 3816kb

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 47ms
memory: 3932kb

input:

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

output:

8
7
8
5
6
8
8
7
6
7
7
6
8
7
8
7
8
7
7
6
7
7
7
5
7
6
5
9
7
7
5
7
7
9
7
6
8
7
8
8
7
7
6
4
7
7
8
7
9
6
7
6
7
8
8
8
8
7
6
7
7
7
7
8
7
7
8
6
7
8
7
7
7
8
6
7
7
7
5
6
7
8
7
6
8
7
7
7
6
7
7
7
7
8
6
8
9
7
8
7
7
6
8
8
7
6
8
7
7
8
8
7
5
7
8
6
7
7
7
8
8
7
7
8
8
8
8
7
7
8
7
8
7
6
7
6
7
8
7
8
7
7
6
7
7
7
7
7
7
8
...

result:

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