QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719834 | #8554. Bot Friends | born_to_sun | WA | 256ms | 5716kb | C++14 | 1.4kb | 2024-11-07 09:18:15 | 2024-11-07 09:18:15 |
Judging History
answer
#include"bits/stdc++.h"
using namespace std;
const int maxn = 5010;
const int Inf = 1e9;
int f[maxn][maxn][3];
char c[maxn];
int T,n;
int G(int x){
return max(0,x);
}
int cnt;
int main(){
ios::sync_with_stdio(0),cin.tie(nullptr);
cin>>T;
while(T--){
cin>>(c+1),n=strlen(c+1);
for(int l=0;l<=n+1;l++)
for(int r=0;r<=n+1;r++)
f[l][r][0]=f[l][r][1]=f[l][r][2]=-Inf;
for(int i=1;i<=n;i++){
if(c[i]!='>')f[i][i][2]=0;
if(c[i]!='<')f[i][i][1]=0;
}
for(int Ln=2;Ln<=n;Ln++)
for(int l=1;l+Ln-1<=n;l++){
int r=l+Ln-1;
if(c[r]!='<')f[l][r][1]=max({f[l][r][1],f[l][r-1][1]});
if(c[l]!='<')f[l][r][1]=max({f[l][r][1],f[l+1][r][2]+1,f[l+1][r][1]});
if(c[r]!='>')f[l][r][2]=max({f[l][r][2],f[l][r-1][1]+1,f[l][r-1][2]});
if(c[l]!='>')f[l][r][2]=max({f[l][r][2],f[l+1][r][2]});
if(n>10) continue;
int lst=f[l][r][1];
for(int k=l;k<r;k++){
// if(f[l][k][1]+f[k+1][r][1]>lst){
// cerr<<l<<" "<<k<<' '<<r<<" "<<f[l][k][1]+f[k+1][r][1]<<' '<<lst<<'\n';
// }
f[l][r][1]=max({f[l][r][1],f[l][k][1]+f[k+1][r][1]});
f[l][r][2]=max({f[l][r][2],f[l][k][2]+f[k+1][r][2]});
}
// if(f[l][r][1]>0) cnt++;
// cerr<<f[l][r][1]<<' ';
}
int Ans=max(f[1][n][1],f[1][n][2]);
for(int k=1;k<n;k++)
Ans=max({Ans,f[1][k][2]+f[k+1][n][1]});
cout<<Ans<<'\n';
// cerr<<cnt<<'\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5716kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 104ms
memory: 3668kb
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 6 5 7 5 8 7 6 8 7 8 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 8 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 8 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:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 89ms
memory: 3632kb
input:
100000 <<<<>>>>>< >>>><<<><< >><?>><<<< <><><<>?<> ><>?>>?<>< <<<<><><>< >>>??<><>< <<><?>?<<< >?<<<><<<< <<>><<><>< <>?<<<<>>< >>?>>>><>> ?>><<?<<<< >>>><><??< ><<<<<><<< ><???<>><> <<<<><<<>> ?<>>?>?<<< <><>><><>> <>><<<<>>< <<>><<<<>> ><><<<<?<< ><<<<<><>> >>>><<><?> ><>>?><?<< ??<?<??<<? <<<<><<...
output:
2 8 8 5 7 3 7 6 6 5 6 4 8 8 4 6 2 8 4 6 4 6 3 7 8 8 3 4 5 7 5 8 7 6 5 6 5 5 6 6 5 7 3 4 7 6 6 5 8 7 5 3 6 4 6 6 3 4 6 6 8 6 6 6 7 4 4 6 6 6 1 5 4 7 6 5 6 4 4 4 5 5 4 6 8 7 4 6 4 4 5 4 7 8 6 6 6 6 4 7 5 6 4 6 6 7 4 2 5 5 6 5 6 6 5 6 4 4 3 8 5 7 5 6 6 6 5 5 7 8 7 5 4 4 5 6 7 5 3 5 5 3 7 7 2 7 6 8 7 2 ...
result:
ok 100000 numbers
Test #4:
score: -100
Wrong Answer
time: 256ms
memory: 3736kb
input:
100000 >>>??><<>?<>??>><>?< >><<>????<<<>?>>?<<< <>>??><><>>?>>?><>?> <<<<><>><>>>???>>>?< <>>>?<>>>?<><??<<<>> >><><><><?<>>><>??>< >?<>?????<?<<><<<<>> ?><<>?>??>>>??<><<?< >>><>?<?>>?<?<??>?>< <>>?<<?>???><?><><>? <>?<?>?>?<>?<????>?< <??<>?<>><<?<?????<< >?>?<><>?<><><>>>??> >?<??>?<??>>>>><><?<...
output:
15 16 11 10 14 13 15 17 15 14 15 15 13 15 13 14 14 14 16 15 15 10 13 12 13 15 15 15 10 14 12 13 12 13 14 10 12 9 14 13 15 12 13 13 16 10 11 14 11 12 12 13 12 15 16 13 15 13 10 16 15 15 13 14 17 14 16 13 14 13 10 14 12 16 14 16 16 13 13 17 14 15 15 12 17 14 10 13 12 15 16 12 14 14 14 14 11 15 13 13 1...
result:
wrong answer 2nd numbers differ - expected: '17', found: '16'