QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719823 | #8554. Bot Friends | born_to_sun | TL | 789ms | 5792kb | C++14 | 1.4kb | 2024-11-07 09:15:14 | 2024-11-07 09:15:14 |
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>1000) 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: 1ms
memory: 5708kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 159ms
memory: 5616kb
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: 113ms
memory: 3608kb
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: 0
Accepted
time: 490ms
memory: 3652kb
input:
100000 >>>??><<>?<>??>><>?< >><<>????<<<>?>>?<<< <>>??><><>>?>>?><>?> <<<<><>><>>>???>>>?< <>>>?<>>>?<><??<<<>> >><><><><?<>>><>??>< >?<>?????<?<<><<<<>> ?><<>?>??>>>??<><<?< >>><>?<?>>?<?<??>?>< <>>?<<?>???><?><><>? <>?<?>?>?<>?<????>?< <??<>?<>><<?<?????<< >?>?<><>?<><><>>>??> >?<??>?<??>>>>><><?<...
output:
15 17 12 12 14 13 15 17 15 14 15 15 13 16 15 16 15 15 17 15 15 10 16 12 14 16 17 16 11 14 13 14 13 14 14 10 12 11 15 13 16 13 13 13 16 10 14 16 12 12 13 14 14 16 17 13 15 15 11 17 15 15 16 15 17 15 16 14 14 13 11 15 14 17 15 17 17 15 13 17 16 16 16 14 17 14 12 14 13 15 16 12 15 16 14 15 13 16 15 14 ...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 476ms
memory: 5644kb
input:
100000 <<>?>>?<>?<>><<<<<>< <>>><<>><><><><<>?>> ><>?<<>><>?<>>><><<> >>>><?><<<<><<<?><<< >>?<><>>?>??<>><<>>< >>?><<?<<><?><<<<>>> ><?<<><>><<?<?>><>?< <><<<?<><<<<<<<>><>< <<><><><>><<<>>>><>< >>>><<?<><<<<><<<>>> <<<><>><<><<>?<<<<>> ><>><>>><>><>?<><??< ?<<><?>><><><><<><>< <>>><><<><?<<<>><><>...
output:
14 11 13 16 15 14 14 9 11 13 11 14 12 13 14 16 10 13 15 12 11 10 8 13 13 11 16 13 14 13 10 14 13 14 13 15 11 11 14 13 12 13 11 11 13 12 10 13 15 13 13 14 6 14 14 8 11 8 14 12 11 10 12 14 14 13 10 13 9 15 16 7 11 14 12 12 12 12 12 15 12 14 10 13 11 14 13 14 14 11 9 12 13 11 12 11 11 16 13 11 13 15 15...
result:
ok 100000 numbers
Test #6:
score: 0
Accepted
time: 547ms
memory: 5640kb
input:
100000 ?>???<<><>?>?>>>><<>? ?>?>>?>><<><??<?<?>?? <><<?>>?<>?<>>?><???? >?<<<?><?>?><>>><>><< <???>?<>???<><<<<<??> ><<?<<<<<<<<<<<?>><<? ?<?>><?<?>?<>??><><>< ?>?<?>>>><<?>??><>>>> ><<<????>>><>>>><<??> <??><??>><<?<?<>>?><> >><>>>><>>?<?<>?>><>> ??<?<<><?>?>>>??><>?> >?<<<?<?><<??><>>?<?? <<>?<?>...
output:
15 18 16 15 16 9 15 13 15 15 14 14 16 16 18 14 16 14 19 16 11 13 14 15 14 17 12 14 14 12 15 16 16 15 18 15 15 16 17 16 14 17 17 15 13 16 14 14 13 16 15 14 16 16 18 14 15 14 15 14 13 17 13 17 13 16 15 15 17 18 18 15 13 15 17 15 17 14 16 14 15 12 16 16 14 17 17 16 18 14 15 14 18 15 15 16 17 15 16 19 1...
result:
ok 100000 numbers
Test #7:
score: 0
Accepted
time: 488ms
memory: 3784kb
input:
100000 <><><><<>><>>><>?<<?> <><<>><>>>>><>><<>?<? >?<<>>><>>>><?<<<>><< >>>><<<<<<>><>>>><<>> <<>>><<>><<?><?>>>><< <<<<><??><<><>>>?>?>> >><><>?>><><<<>>><<>? ><<<>>><<><<><><><>>< >>><>>?><<<<?><<<<<?< ?<>>><<><<><><<>><<>< <<><<<><<<<>>>>>>>>>> <?<><<>><><>>><<>>><> <<>><><>>><><>>><<><< ><<><<>...
output:
13 15 17 14 14 10 15 13 18 14 4 12 13 13 12 15 14 14 14 12 14 15 14 10 12 11 15 6 14 14 14 12 17 14 12 16 13 14 13 8 12 14 13 14 12 15 14 14 14 12 17 17 15 12 14 15 13 12 13 16 13 16 16 14 15 15 17 11 14 13 11 12 12 10 14 14 15 12 12 15 13 14 14 12 15 15 15 10 15 16 15 13 16 14 14 10 18 10 14 11 8 1...
result:
ok 100000 numbers
Test #8:
score: 0
Accepted
time: 624ms
memory: 3776kb
input:
100000 ??><>?<?><<<<>>??>><<< ?<><><<??<<<>><?><>?<> <><<>?><>?>><>??>?<<?> >>><??<?<>>>>>><??><<? >?<<><??<>?>>?<<?>>?<> ?<?>?>?<><?>?<?<?>>>?< ?<?<<><<<?<>>?<><<><>? ?>>><?<<>?>>>?<??>>?>> >>???>???<>?<??><?>?>< ?>>?>>>><>>?><>?>?<<>? ><?<?<<<?<<?<>??<>>?<< >?<?<<<<???<?<<?<<?<<< >><>>>><<>>?>?>??...
output:
17 14 15 18 16 17 14 17 17 16 15 16 16 15 17 16 18 13 13 15 16 17 18 16 16 18 14 19 18 15 18 17 16 17 16 16 18 17 17 17 16 16 14 17 15 16 18 16 16 18 16 17 16 17 16 12 17 15 17 16 16 16 17 16 16 18 17 16 18 18 15 17 19 18 19 17 16 15 17 17 16 16 18 13 12 19 17 19 16 16 18 16 17 18 14 15 16 18 10 14 ...
result:
ok 100000 numbers
Test #9:
score: 0
Accepted
time: 547ms
memory: 3664kb
input:
100000 ?><?><<<?<><<<>>><<>>> ><><<<>?><><???>><>><< <><>>><>>>>>>>>>><<><< <>>>><<<<<<><<<<<>>?>< ><<><>><?>>>>><>>><>>< <?<<<<<>><<>>>>><?<><< <?<<<><<>>>>><<<><>>>< ><<><<>><<<<><<><<>>?< >><<<><<<<<>>>>><<?>>< >?<<?<<<?<<<<<>?<<<>>> <>?<>>>?<><><>>>><><<> ><<?<?<<<<>>><><<>><<? <>>><>?>>>><><>>>...
output:
14 16 11 13 12 14 14 15 14 12 14 15 14 13 13 15 15 16 17 11 16 15 17 17 14 16 12 13 15 16 11 17 14 18 16 16 16 14 13 13 14 16 16 16 17 16 16 16 15 15 16 10 9 14 16 16 13 14 16 15 16 14 13 17 16 16 17 15 17 13 14 12 13 11 10 13 14 15 11 15 17 13 17 14 16 12 15 11 15 15 14 15 12 16 17 14 17 16 12 13 1...
result:
ok 100000 numbers
Test #10:
score: 0
Accepted
time: 789ms
memory: 5792kb
input:
20000 ?<?><??>>?<?><<>>?>?>?>?<<<><???<?<<<><?<?<>>?<><> ????><??><>??<><????><>?<>?<?><<<><>?<>??<?<<?><<> >?>>?>>>>>>?<<??<??<?<?>>><??<<>>>?<<?<<>?<<<>>><? ?<<>>?>>><?><<><?><>>?><?<<?<>????<>><<<<?>><<>??< ?????>>>>?>?><<>??>>>?<><?>><??????>>>?<>??>>????? >>>?<?<<?<>>>????<<?>><><>>><>?<?<>><>>...
output:
40 37 45 40 43 40 38 40 37 41 42 35 41 40 38 40 37 39 40 39 40 42 42 41 43 39 35 41 41 39 40 41 35 42 38 40 37 39 41 38 37 39 37 42 38 40 42 37 43 42 41 38 41 41 40 42 42 39 36 41 42 45 40 41 38 37 37 37 38 37 41 39 39 42 38 40 37 39 40 37 42 38 41 40 39 37 39 40 37 38 39 37 37 41 37 39 39 39 42 38 ...
result:
ok 20000 numbers
Test #11:
score: -100
Time Limit Exceeded
input:
5000 <<???<<?<>>>?<<<<>?<><>?><??<?<><<><?><>>><<><?>>?>>?>??>?>>?<<?<<<?>?><>><<<>>>?<<<<<>??>>>>?><>>?< >?<>?>><?<?>>??>????>>??>?>????>>?>>???>????<?><<>><<<<>?<<?<??><>><?<?<>??<<>>><<<<<?>>??<?<<>>>?>> <>><?><???>??<?????><><?>><?>><???<?<><?<>?<???<<?>>????>?<?<<><<<>>?>>?><>??<?>?<><>><??<>>?...
output:
80 85 82 88 78 78 81 79 86 79 80 79 82 76 81 78 84 78 80 81 82 80 81 78 81 87 81 85 83 85 84 83 82 79 82 83 82 83 82 84 78 81 77 77 84 82 74 83 80 80 83 84 80 80 75 81 80 82 81 83 79 78 82 85 80 82 85 83 81 79 84 80 86 84 82 79 81 78 83 81 82 83 77 83 84 85 81 81 79 83 84 85 83 82 84 84 78 77 83 74 ...