QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733221 | #8554. Bot Friends | hhoppitree | TL | 997ms | 8164kb | C++17 | 1.3kb | 2024-11-10 17:45:09 | 2024-11-10 17:45:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5, P = 998244353;
int f[N][N][2];
void upd(int &x, int y) {
(y < x) && (x = y);
}
signed main() {
int T; scanf("%d", &T);
while (T--) {
string s, S; cin >> s;
int n = s.size(), tn = n;
for (int i = 0; i < n; ++i) {
S += '?';
S += s[i];
}
S += '?';
n = S.size(), S = ' ' + S + ' ';
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= i; ++j) {
f[i][j][0] = f[i][j][1] = 1e9;
}
}
f[0][0][1] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 0; k < 2; ++k) {
for (int l = 0; l < 3; ++l) {
if ((S[i + 1] == '<' && l == 0) || (S[i + 1] == '>' && l == 1) || (((i & 1) || j != 0) && l == 2)) {
continue;
}
int tj = j + (l == 0 ? 1 : (l == 1 ? -1 : 0));
if (~tj) upd(f[i + 1][tj][min(l, 1)], f[i][j][k] + (k == 0 && l == 1));
}
}
}
}
printf("%d\n", tn - f[n][0][1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5920kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 342ms
memory: 5888kb
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: 298ms
memory: 5848kb
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: 997ms
memory: 7940kb
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: 996ms
memory: 8164kb
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: -100
Time Limit Exceeded
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...