QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#389998#8554. Bot Friendsucup-team1191#TL 849ms4068kbC++203.4kb2024-04-14 23:31:112024-04-14 23:31:11

Judging History

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

  • [2024-04-14 23:31:11]
  • 评测
  • 测评结果:TL
  • 用时:849ms
  • 内存:4068kb
  • [2024-04-14 23:31:11]
  • 提交

answer

// !!!!!!
// rename to template.cpp instead of main.cpp
#include <bits/stdc++.h>

#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
                    .time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)
template<typename T, typename U>
ostream& operator << (ostream& o, const pair<T, U>& p) {
    return o << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
ostream& operator << (ostream& o, const vector<T>& v) {
    bool first = true;
    o << "[";
    for (const auto& l : v) {
        if (!first) o << ", ";
        o << l;
        first = false;
    }
    return o << "]";
}
template<typename T>
ostream& operator << (ostream& o, const set<T>& v) {
    bool first = true;
    o << "{";
    for (const auto& l : v) {
        if (!first) o << ", ";
        o << l;
        first = false;
    }
    return o << "}";
}
#ifdef ONPC
#define show(x) cout << "LINE " << __LINE__ << ": " << #x << "=" << x << std::endl;
#else
#define show(x) 42
#endif

using ll = long long;
using ld = double;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    const int inf = 1e9;
    vector<vector<array<int, 3>>> dp(n, vector<array<int, 3>>(n, {inf, inf, inf}));
    // {left, middle, right}
    for (int i = 0; i < n; ++i) {
        if (s[i] == '<') {
            dp[i][i][2] = 1;
        } else if (s[i] == '>') {
            dp[i][i][0] = 1;
        } else {
            dp[i][i][0] = dp[i][i][2] = 1;
        }
    }
    for (int len = 2; len <= n; ++len) {
        for (int l = 0; l < n; ++l) {
            int r = l + len - 1;
            if (r >= n) break;
            for (int m = l; m < r; ++m) {
                dp[l][r][0] = min(dp[l][r][0], dp[l][m][0] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][1] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][0]);
                dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][1]);
                dp[l][r][2] = min(dp[l][r][2], dp[l][m][2] + dp[m + 1][r][2]);
            }
            if (s[l] == '>' || s[l] == '?') {
                for (int b = 0; b < 3; ++b) {
                    dp[l][r][0] = min(dp[l][r][0], dp[l + 1][r][b] + (b == 0));
                }
            }
            if (s[l] == '<' || s[l] == '?') {
                for (int b = 0; b < 3; ++b) {
                    dp[l][r][max(1, b)] = min(dp[l][r][max(1, b)], dp[l + 1][r][b] + 1);
                }
            }
            if (s[r] == '<' || s[r] == '?') {
                for (int b = 0; b < 3; ++b) {
                    dp[l][r][2] = min(dp[l][r][2], dp[l][r - 1][b] + (b == 2));
                }
            }
            if (s[r] == '>' || s[r] == '?') {
                for (int b = 0; b < 3; ++b) {
                    dp[l][r][min(1, b)] = min(dp[l][r][min(1, b)], dp[l][r - 1][b] + 1);
                }
            }
        }
    }
    cout << n - *min_element(all(dp[0][n-1])) << '\n';
}

int main() {
#ifdef ONPC
    freopen("input", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0);
    cout << fixed << setprecision(20);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    cerr << "\n\nConsumed " << TIME << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3876kb

input:

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: 0
Accepted
time: 155ms
memory: 4068kb

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: 132ms
memory: 3948kb

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: 664ms
memory: 3996kb

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: 626ms
memory: 3956kb

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: 749ms
memory: 3952kb

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: 695ms
memory: 3964kb

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: 849ms
memory: 3896kb

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: 794ms
memory: 3960kb

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: -100
Time Limit Exceeded

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: