QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#722337 | #8554. Bot Friends | KellyWLJ | WA | 71ms | 5816kb | C++17 | 2.3kb | 2024-11-07 18:39:23 | 2024-11-07 18:39:23 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N = 5010;
template<typename T>
void print(T x) {
if(x < 0) putchar('-'), x = -x;
if(x / 10) print(x / 10);
putchar(x % 10 + '0');
}
int n, a[N], f[N][N][2], g[N][N][2], ans;
char s[N];
void chkmax(int &a, int b) {a < b && (a = b);}
void mian() {
cin >> (s + 1), n = strlen(s + 1), ans = 0;
for(int i = 0; i <= n + 1; ++i)
for(int j = 0; j <= n + 1; ++j) f[i][j][0] = f[i][j][1] = g[i][j][0] = g[i][j][1] = -N;
f[n + 1][0][1] = 0;
for(int i = n; i > 0; --i) {
for(int j = 0; j <= n - i; ++j) {
if(s[i] != '>') chkmax(f[i][j + 1][1], max(f[i + 1][j][0], f[i + 1][j][1])); // i to left
if(s[i] != '<') { // i to right
chkmax(f[i][j][0], f[i + 1][j][1]);
chkmax(f[i][j][0], f[i + 1][j][0]);
if(j) chkmax(f[i][j - 1][0], f[i + 1][j][0] + 2), chkmax(f[i][j - 1][0], f[i + 1][j][1] + 1);
}
// cerr << f[i + 1][j][0] << " " << f[i + 1][j][1] << " ";
}
// cerr << "\n";
}
g[0][0][1] = 0;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < i; ++j) {
if(s[i] != '<') chkmax(g[i][j + 1][1], max(g[i - 1][j][0], g[i - 1][j][1])); // i to right
if(s[i] != '>') { // i to left
chkmax(g[i][j][0], g[i - 1][j][1]);
chkmax(g[i][j][0], g[i - 1][j][0]);
if(j) chkmax(g[i][j - 1][0], g[i - 1][j][0] + 2), chkmax(g[i][j - 1][0], g[i + 1][j][1] + 1);
}
// cerr << g[i][j][0] << " " << g[i][j][1] << " ";
}
// cerr << "\n";
}
for(int i = 0; i <= n; ++i) {
int tmp = 0, res = 0;
for(int j = 0; j < i; ++j) chkmax(tmp, max(g[i][j][0], g[i][j][1]));
for(int j = 0; j <= n - i; ++j) chkmax(res, max(f[i + 1][j][0], f[i + 1][j][1]));
chkmax(ans, tmp + res);
}
print(ans), putchar('\n');
}
int main() {
#ifdef Kelly
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
freopen("err.txt", "w", stderr);
#endif
ios::sync_with_stdio(false), cin.tie(nullptr);
int T = 1; cin >> T;
while(T--) mian();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5724kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 71ms
memory: 5816kb
input:
100000 >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?> >><>><<<<< >?>?>?<<>> ?><?<<?<>< ???><>?>?> <??>?<<><? ??>><?<>>> <><><?<>>? ?>>?>???>< ?<?><?<<>? >>><?<??>< ><><<>?>?< >?><>><<<? >??>?><?<> ?????<><?> <><<?<<>?< ><?>>?>?>? ?><><<<>>? ?<>?<>?<<< <><<<<<>>> ?>?>?><<>> <>?<>><>?< <<<?<>>...
output:
8 7 8 5 6 8 6 7 6 7 6 6 8 7 8 6 8 7 7 6 6 6 7 2 6 6 3 9 6 6 5 7 5 8 6 5 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 6 6 8 5 7 6 6 5 5 7 7 6 4 8 6 6 7 5 7 6 6 6 8 3 8 8 7 8 7 6 4 8 8 7 5 8 6 7 8 8 7 5 6 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:
wrong answer 16th numbers differ - expected: '7', found: '6'