QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#456266 | #8554. Bot Friends | kkkgjyismine4 | WA | 102ms | 8088kb | C++23 | 1.5kb | 2024-06-27 16:42:22 | 2024-06-27 16:42:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9;
int n;char s[5050];
int f[5050][5050][2][2],g[5050][5050][2][2];
void upd(int &x,const int y){x=((x>y)?x:y);}
void solve(){
scanf("%s",s+1),n=strlen(s+1);
for(int i=0;i<=n+1;++i)for(int j=0;j<=n+1;++j)for(int a=0;a<2;++a)for(int b=0;b<2;++b)f[i][j][a][b]=g[i][j][a][b]=-inf;
f[0][0][0][0]=g[n+1][0][0][0]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<i;++j)
for(int k=0;k<2;++k)
for(int o=0;o<2;++o)
if(f[i-1][j][k][o]>=0){
if(s[i]!='<')upd(f[i][j+1][1][0],f[i-1][j][k][o]+1);
if(s[i]!='>'){
if(!j)upd(f[i][0][0][0],f[i-1][j][k][o]+k);
else{
if(i==1||o)upd(f[i][j-1][1][1],f[i-1][j][k][o]+1);
else upd(f[i][j-1][1][1],f[i-1][j][k][o]);
}
}
}
for(int i=n;i>=1;--i)
for(int j=0;j<n-i+1;++j)
for(int k=0;k<2;++k)
for(int o=0;o<2;++o)
if(g[i+1][j][k][o]>=0){
if(s[i]!='>')upd(g[i][j+1][1][0],g[i+1][j][k][o]+1);
if(s[i]!='<'){
if(!j)upd(g[i][0][0][0],g[i+1][j][k][o]+k);
else{
if(i==1||o)upd(g[i][j-1][1][1],g[i+1][j][k][o]+1);
else upd(g[i][j-1][1][1],g[i+1][j][k][o]);
}
}
}
int ans=0;
for(int i=0;i<=n;++i)
for(int a=0;a<2;++a)
for(int b=0;b<2;++b)
for(int c=0;c<2;++c)
for(int d=0;d<2;++d)upd(ans,f[i][0][a][b]+g[i+1][0][c][d]);
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8088kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 102ms
memory: 8040kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 7 7 6 6 7 6 5 7 7 8 7 8 8 7 6 6 7 8 2 6 6 3 9 6 5 5 8 5 8 7 6 8 7 7 6 6 7 4 2 7 5 7 7 9 6 7 5 7 8 8 8 8 7 5 6 7 8 7 8 7 5 8 6 7 9 7 7 6 9 5 8 6 6 5 5 7 8 5 3 8 6 5 8 5 7 5 7 7 8 3 8 9 7 8 7 7 4 8 8 7 5 9 6 8 7 8 7 5 7 8 5 7 6 6 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 8 ...
result:
wrong answer 6th numbers differ - expected: '8', found: '7'