QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#464038 | #8554. Bot Friends | PhantomThreshold# | WA | 55ms | 3848kb | C++20 | 1.0kb | 2024-07-05 17:47:05 | 2024-07-05 17:47:05 |
Judging History
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'