QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#464038#8554. Bot FriendsPhantomThreshold#WA 55ms3848kbC++201.0kb2024-07-05 17:47:052024-07-05 17:47:05

Judging History

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

  • [2024-07-05 17:47:05]
  • 评测
  • 测评结果:WA
  • 用时:55ms
  • 内存:3848kb
  • [2024-07-05 17:47:05]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	const int inf=1e9;
	auto up=[](int &x,int y){x=max(x,y);};
	int T;
	cin>>T;
	while(T--)
	{
		string s;
		cin>>s;
		int n=(int)s.length();
		s=' '+s;
		//0:>, 1:<
		vector<vector<int>> dp(2,vector<int>(n+5,-inf)),pd=dp;
		dp[1][0]=0;
		for(int i=1;i<=n;i++)
		{
			fill(pd[0].begin(),pd[0].end(),-inf);
			fill(pd[1].begin(),pd[1].end(),-inf);
			if(s[i]!='<')
			{
				for(int j=0;j<=n;j++)
				{
					up(pd[0][max(j+1,2)],dp[0][j]);
					if(j>1)up(pd[0][j],dp[1][j]+1);
					else up(pd[0][max(j+1,2)],dp[1][j]);
				}
			}
			if(s[i]!='>')
			{
				for(int j=0;j<=n;j++)
				{
					if(j)up(pd[1][j-1],dp[0][j]+1);
					if(j>1)up(pd[1][j-1],dp[1][j]+2);
					else if(j==1)up(pd[1][j-1],dp[1][j]+1);
					else up(pd[1][j],dp[1][j]);
				}
			}
			
			dp.swap(pd);
		}
		int ans=0;
		for(int j=0;j<=n;j++)
		{
			ans=max(ans,dp[0][j]);
			ans=max(ans,dp[1][j]+(j>1));
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 55ms
memory: 3848kb

input:

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

output:

8
7
8
5
6
6
6
6
6
7
6
5
8
6
8
7
8
7
7
6
6
6
7
2
6
6
3
9
6
5
5
7
5
8
6
5
8
7
7
6
6
7
4
2
7
5
8
7
8
5
6
5
7
8
8
8
8
7
5
5
7
7
6
8
7
5
8
6
6
8
7
7
6
8
5
7
6
6
5
5
7
7
5
3
8
6
5
7
5
7
6
7
6
8
3
8
8
6
8
7
6
4
8
8
7
5
8
6
7
7
8
7
5
7
8
5
7
6
5
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
7
...

result:

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