QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719834#8554. Bot Friendsborn_to_sunWA 256ms5716kbC++141.4kb2024-11-07 09:18:152024-11-07 09:18:15

Judging History

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

  • [2024-11-07 09:18:15]
  • 评测
  • 测评结果:WA
  • 用时:256ms
  • 内存:5716kb
  • [2024-11-07 09:18:15]
  • 提交

answer

#include"bits/stdc++.h"
using namespace std;
const int maxn = 5010;
const int Inf = 1e9;
int f[maxn][maxn][3];
char c[maxn];
int T,n;
int G(int x){
	return max(0,x);
}
int cnt;
int main(){
	ios::sync_with_stdio(0),cin.tie(nullptr);
	cin>>T;
	while(T--){
		cin>>(c+1),n=strlen(c+1);
		for(int l=0;l<=n+1;l++)
			for(int r=0;r<=n+1;r++)
				f[l][r][0]=f[l][r][1]=f[l][r][2]=-Inf;
		for(int i=1;i<=n;i++){
			if(c[i]!='>')f[i][i][2]=0;
			if(c[i]!='<')f[i][i][1]=0;
		}
		for(int Ln=2;Ln<=n;Ln++)
			for(int l=1;l+Ln-1<=n;l++){
				int r=l+Ln-1;
				if(c[r]!='<')f[l][r][1]=max({f[l][r][1],f[l][r-1][1]});
				if(c[l]!='<')f[l][r][1]=max({f[l][r][1],f[l+1][r][2]+1,f[l+1][r][1]});
				if(c[r]!='>')f[l][r][2]=max({f[l][r][2],f[l][r-1][1]+1,f[l][r-1][2]});
				if(c[l]!='>')f[l][r][2]=max({f[l][r][2],f[l+1][r][2]});
				if(n>10) continue;
				int lst=f[l][r][1];
				for(int k=l;k<r;k++){
					// if(f[l][k][1]+f[k+1][r][1]>lst){
					// 	cerr<<l<<" "<<k<<' '<<r<<" "<<f[l][k][1]+f[k+1][r][1]<<' '<<lst<<'\n';
					// }
					f[l][r][1]=max({f[l][r][1],f[l][k][1]+f[k+1][r][1]});
					f[l][r][2]=max({f[l][r][2],f[l][k][2]+f[k+1][r][2]});
				}
				// if(f[l][r][1]>0) cnt++;
				// cerr<<f[l][r][1]<<' ';
			}
		int Ans=max(f[1][n][1],f[1][n][2]);
		for(int k=1;k<n;k++)
			Ans=max({Ans,f[1][k][2]+f[k+1][n][1]});
		cout<<Ans<<'\n';
		// cerr<<cnt<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5716kb

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 104ms
memory: 3668kb

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
6
5
7
5
8
7
6
8
7
8
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
8
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
8
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:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 89ms
memory: 3632kb

input:

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

output:

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

result:

ok 100000 numbers

Test #4:

score: -100
Wrong Answer
time: 256ms
memory: 3736kb

input:

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

output:

15
16
11
10
14
13
15
17
15
14
15
15
13
15
13
14
14
14
16
15
15
10
13
12
13
15
15
15
10
14
12
13
12
13
14
10
12
9
14
13
15
12
13
13
16
10
11
14
11
12
12
13
12
15
16
13
15
13
10
16
15
15
13
14
17
14
16
13
14
13
10
14
12
16
14
16
16
13
13
17
14
15
15
12
17
14
10
13
12
15
16
12
14
14
14
14
11
15
13
13
1...

result:

wrong answer 2nd numbers differ - expected: '17', found: '16'