QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #399058 | #8554. Bot Friends | Bronya | WA | 38ms | 6012kb | C++14 | 651b | 2024-04-25 21:16:39 | 2024-04-25 21:16:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
char s[5005];
int dp[5005][5005];
int f[5005];
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
int n=strlen(s+1);
for(int i=0;i<=n;i++)dp[i+1][i]=0;
f[0]=0;
for(int i=1;i<=n;i++){
f[i]=n;
for(int j=i;j>=1;j--){
dp[j][i]=min(dp[j+1][i]+1,dp[j][i-1]+1);
if(s[i]!='>'&&s[j]!='<')dp[j][i]=min(dp[j][i],dp[j+1][i-1]);
f[i]=min(f[i],f[j-1]+1+dp[j][i]);
f[i]=min(f[i],f[j-1]+1+dp[j][i-1]+(s[i]=='>'));
f[i]=min(f[i],f[j-1]+1+dp[j+1][i]+(s[j]=='<'));
}
}
// printf("%d\n",dp[5][8]);
printf("%d\n",n-f[n]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6012kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 38ms
memory: 4000kb
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 5 5 7 5 8 7 6 8 7 7 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 7 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 7 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:
wrong answer 30th numbers differ - expected: '6', found: '5'