QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#399062 | #8554. Bot Friends | Bronya | WA | 30ms | 3908kb | C++14 | 756b | 2024-04-25 21:19:42 | 2024-04-25 21:19:49 |
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);
int sb=0;
while(T--){sb++;
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]=='<'));
}
}
if(sb==30){
for(int i=1;i<=n;i++)putchar(s[i]);
putchar('\n');
}
// printf("%d\n",dp[5][8]);
if(T<=10)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: 0ms
memory: 3908kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 30ms
memory: 3872kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
>><<?<??>> 6 8 5 6 8 7 6 7 7 8 8
result:
wrong output format Expected integer, but ">><<?<??>>" found