QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#576604#8554. Bot Friendsucup-team4435#WA 197ms3748kbC++202.6kb2024-09-19 21:13:202024-09-19 21:13:22

Judging History

你现在查看的是最新测评结果

  • [2024-09-19 21:13:22]
  • 评测
  • 测评结果:WA
  • 用时:197ms
  • 内存:3748kb
  • [2024-09-19 21:13:20]
  • 提交

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'