QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#474397#8554. Bot Friendsreal_sigma_team#WA 89ms3692kbC++201.6kb2024-07-12 17:50:232024-07-12 17:50:24

Judging History

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

  • [2024-07-12 17:50:24]
  • 评测
  • 测评结果:WA
  • 用时:89ms
  • 内存:3692kb
  • [2024-07-12 17:50:23]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define x first
#define y second

void solve();

int main() {
#ifndef LOCAL
	cin.tie(nullptr)->sync_with_stdio(false);
#endif
	cout << fixed << setprecision(30);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
}

const int N = 5000;

int dp[N][N][3]; //0 - mid, 1 - left, 2 - right


void solve() {
	string s;
	cin >> s;
	int n = s.size();
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			for (int c = 0; c < 3; ++c) {
				dp[i][j][c] = -1e9;
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		if (s[i] != '<') {
			dp[i][i][1] = 0;
		}
		if (s[i] != '>') {
			dp[i][i][2] = 0;
		}
	}
	for (int len = 1; len < n; ++len) {
		for (int l = 0, r = len; r < n; ++l, ++r) {
			if (s[l] != '<') {
				for (int c = 0; c < 3; ++c) {
					dp[l][r][1] = max(dp[l][r][1], dp[l + 1][r][c] + (c != 1));
				}
			}
			if (s[l] != '>') {
				for (int c = 0; c < 3; ++c) {
					int q = (c == 2 ? 2 : 0);
					dp[l][r][q] = max(dp[l][r][q], dp[l + 1][r][c]);
				}
			}
			if (s[r] != '<') {
				for (int c = 0; c < 3; ++c) {
					int q = (c == 1 ? 1 : 0);
					dp[l][r][q] = max(dp[l][r][q], dp[l][r - 1][c]);
				}
			}
			if (s[r] != '>') {
				for (int c = 0; c < 3; ++c) {
					dp[l][r][2] = max(dp[l][r][2], dp[l][r - 1][c] + (c != 2));
				}
			}
			// cout << l << ' ' << r;
			// for (int c = 0; c < 3; ++c) cout << ' ' << dp[l][r][c];
			// cout << endl;
		}
	}
	vector<int> dp2(n + 1, 0);
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			for (int c = 0; c < 3; ++c) {
				dp2[j + 1] = max(dp2[j + 1], dp2[i] + dp[i][j][c]);
			}
		}
	}
	cout << dp2.back() << '\n';
}
//>?>?>?<<>>

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3692kb

input:

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

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 89ms
memory: 3636kb

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'