QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404376 | #8554. Bot Friends | yyyyxh | WA | 48ms | 3716kb | C++14 | 997b | 2024-05-03 21:23:47 | 2024-05-03 21:23:47 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=5003,INF=0x3f3f3f3f;
char s[N];
int n;
int f[N][N],g[N][N];
inline void chmn(int &x,int v){if(x>v) x=v;}
void solve(){
scanf("%s",s+1);
n=strlen(s+1);
for(int i=0;i<=n;++i)
for(int j=0;j<=i;++j) f[i][j]=g[i][j]=INF;
f[0][0]=0;
for(int i=1;i<=n;++i)
for(int j=0;j<i;++j){
if(s[i]!='<'){
chmn(f[i][j+1],f[i-1][j]);
chmn(f[i][j],g[i-1][j]);
chmn(f[i][j],f[i-1][j]+1);
if(j) chmn(g[i][j],f[i-1][j]+1);
chmn(g[i][j],g[i-1][j]+1);
}
if(s[i]!='>'){
chmn(f[i][j],f[i-1][j]+1);
chmn(g[i][j],g[i-1][j]+1);
if(j) chmn(g[i][j],f[i-1][j]+1);
if(j>1) chmn(g[i][j-1],g[i-1][j]);
else if(j) chmn(f[i][0],g[i-1][j]);
if(j>1) chmn(g[i][j-1],f[i-1][j]+1);
else if(j) chmn(f[i][0],f[i-1][j]+1);
}
}
printf("%d\n",n-min(f[n][0],g[n][1]));
}
int main(){
int tc;
scanf("%d",&tc);
while(tc--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 48ms
memory: 3716kb
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 3 7 6 4 9 6 6 5 7 7 8 7 6 8 7 7 7 6 7 4 2 7 7 8 7 9 6 7 6 7 8 8 8 8 7 6 7 7 7 6 8 7 6 8 6 7 8 7 7 7 8 5 7 6 7 5 5 7 7 6 5 8 6 6 7 6 7 7 7 7 8 4 8 9 7 8 7 7 4 8 8 7 5 8 7 7 8 8 7 5 7 8 6 7 6 6 8 8 7 7 8 7 7 8 7 7 8 7 8 7 6 6 5 7 8 6 8 6 7 6 7 5 7 7 7 7 7 ...
result:
wrong answer 7th numbers differ - expected: '6', found: '8'