QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576604 | #8554. Bot Friends | ucup-team4435# | WA | 197ms | 3748kb | C++20 | 2.6kb | 2024-09-19 21:13:20 | 2024-09-19 21:13:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define all(a) begin(a), end(a)
#define len(a) int((a).size())
template<typename A, typename B>
bool setmax(A &a, const B &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
void solve(int /* test_num */) {
string s;
cin >> s;
int n = len(s);
vector<int> a(n);
for (int i = 0; i < n; i++) {
if (s[i] == '<') {
a[i] = -1;
} else if (s[i] == '?') {
a[i] = 0;
} else if (s[i] == '>') {
a[i] = 1;
}
}
constexpr int INF = 1e9;
vector dp(n, vector<array<int, 3>>(n, {-INF, -INF, -INF}));
for (int i = 0; i < n; i++) {
for (int x : {-1, 1}) {
if (a[i] != 0 && a[i] != x) {
continue;
}
int where = x == -1 ? 2 : 0;
setmax(dp[i][i][where], 0);
}
}
for (int d = 1; d < n; d++) {
for (int l = 0; l + d < n; l++) {
int r = l + d;
for (int tr : {-1, 1}) {
if (a[r] != 0 && a[r] != tr) {
continue;
}
for (int prv : {0, 1, 2}) {
int cost = dp[l][r - 1][prv];
int nxt;
if (tr == -1) {
cost += prv != 2;
nxt = 2;
} else {
nxt = min(prv, 1);
}
setmax(dp[l][r][nxt], cost);
}
}
for (int tl : {-1, 1}) {
if (a[l] != 0 && a[l] != tl) {
continue;
}
for (int prv : {0, 1, 2}) {
int cost = dp[l + 1][r][prv];
int nxt;
if (tl == 1) {
cost += prv != 0;
nxt = 0;
} else {
nxt = max(prv, 1);
}
setmax(dp[l][r][nxt], cost);
}
}
}
}
vector<int> pref_dp(n + 1, -INF);
pref_dp[0] = 0;
for (int r = 0; r < n; r++) {
for (int l = 0; l <= r; l++) {
setmax(pref_dp[r + 1], pref_dp[l] + *max_element(all(dp[l][r])));
}
}
cout << pref_dp[n] << '\n';
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int tests;
cin >> tests;
for (int test_num = 1; test_num <= tests; test_num++) {
solve(test_num);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3748kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 197ms
memory: 3556kb
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 5 5 7 5 8 7 6 8 7 7 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 7 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 7 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 30th numbers differ - expected: '6', found: '5'