QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #390010 | #8554. Bot Friends | ucup-team1191# | TL | 352ms | 3824kb | C++20 | 9.0kb | 2024-04-14 23:56:40 | 2024-04-14 23:56:41 |
Judging History
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;
}
}
vector<vector<array<int, 5>>> opt(n, vector<array<int, 5>>(n, {-1, -1, -1, -1, -1}));
for (int len = 2; len <= n; ++len) {
for (int l = 0; l < n; ++l) {
int r = l + len - 1;
if (r >= n) break;
{
int L = l;
int R = r - 1;
if (len > 2) {
L = opt[l][r - 1][0];
R = opt[l + 1][r][0];
if (L == -1 || R == -1) {
L = l; R = r - 1;
}
L = max(L, l);
R = min(R, r - 1);
}
if (R < L) R = L;
// L = l; R = r - 1;
//L = max(l, L - 10);
//R = min(r - 1, R + 10);
for (int m = L; m <= R; ++m) {
if (dp[l][r][0] > dp[l][m][0] + dp[m + 1][r][0]) {
dp[l][r][0] = dp[l][m][0] + dp[m + 1][r][0];
opt[l][r][0] = m;
}
}
}
{
int L = l;
int R = r - 1;
if (len > 2) {
L = opt[l][r - 1][1];
R = opt[l + 1][r][1];
if (L == -1 || R == -1) {
L = l; R = r - 1;
}
L = max(L, l);
R = min(R, r - 1);
}
if (R < L) R = L;
// L = l; R = r - 1;
//L = max(l, L - 10);
//R = min(r - 1, R + 10);
int opt_val = 1e9;
for (int m = L; m <= R; ++m) {
int cur = dp[l][m][1] + dp[m + 1][r][0];
if (opt_val > cur) {
opt_val = cur;
opt[l][r][1] = m;
}
}
dp[l][r][1] = min(dp[l][r][1], opt_val);
}
{
int L = l;
int R = r - 1;
if (len > 2) {
L = opt[l][r - 1][2];
R = opt[l + 1][r][2];
if (L == -1 || R == -1) {
L = l; R = r - 1;
}
L = max(L, l);
R = min(R, r - 1);
}
if (R < L) R = L;
// L = l; R = r - 1;
//L = max(l, L - 10);
//R = min(r - 1, R + 10);
int opt_val = 1e9;
for (int m = L; m <= R; ++m) {
int cur = dp[l][m][2] + dp[m + 1][r][1];
if (opt_val > cur) {
opt_val = cur;
opt[l][r][2] = m;
}
}
dp[l][r][1] = min(dp[l][r][1], opt_val);
}
{
int L = l;
int R = r - 1;
if (len > 2) {
L = opt[l][r - 1][3];
R = opt[l + 1][r][3];
if (L == -1 || R == -1) {
L = l; R = r - 1;
}
L = max(L, l);
R = min(R, r - 1);
}
if (R < L) R = L;
// L = l; R = r - 1;
L = max(l, L - 100);
R = min(r - 1, R + 100);
int opt_val = 1e9;
for (int m = L; m <= R; ++m) {
int cur = dp[l][m][2] + dp[m + 1][r][0];
if (opt_val > cur) {
opt_val = cur;
opt[l][r][3] = m;
}
}
dp[l][r][1] = min(dp[l][r][1], opt_val);
}
{
int L = l;
int R = r - 1;
if (len > 2) {
L = opt[l][r - 1][4];
R = opt[l + 1][r][4];
if (L == -1 || R == -1) {
L = l; R = r - 1;
}
L = max(L, l);
R = min(R, r - 1);
}
if (R < L) R = L;
// L = l; R = r - 1;
//L = max(l, L - 10);
//R = min(r - 1, R + 10);
for (int m = L; m <= R; ++m) {
if (dp[l][r][2] > dp[l][m][2] + dp[m + 1][r][2]) {
dp[l][r][2] = dp[l][m][2] + dp[m + 1][r][2];
opt[l][r][4] = m;
}
}
}
/*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][1]);
dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][0]);
dp[l][r][2] = min(dp[l][r][2], dp[l][m][2] + dp[m + 1][r][2]);
}*/
/*for (int m = r - 1; 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][1]);
dp[l][r][1] = min(dp[l][r][1], dp[l][m][2] + dp[m + 1][r][0]);
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) {
int cur = dp[l + 1][r][b] + (b == 0);
if (dp[l][r][0] > cur) {
dp[l][r][0] = cur;
//opt[l][r][0] = l;
}
}
}
if (s[l] == '<' || s[l] == '?') {
for (int b = 0; b < 3; ++b) {
int cur = dp[l + 1][r][b] + 1;
if (dp[l][r][max(1, b)] > cur) {
dp[l][r][max(1, b)] = cur;
//opt[l][r][max(1, b)] = l;
}
}
}
if (s[r] == '<' || s[r] == '?') {
for (int b = 0; b < 3; ++b) {
int cur = dp[l][r - 1][b] + (b == 2);
if (dp[l][r][2] > cur) {
dp[l][r][2] = cur;
//opt[l][r][2] = r - 1;
}
}
}
if (s[r] == '>' || s[r] == '?') {
for (int b = 0; b < 3; ++b) {
int cur = dp[l][r - 1][b] + 1;
if (dp[l][r][min(1, b)] > cur) {
dp[l][r][min(1, b)] = cur;
//opt[l][r][min(1, b)] = r - 1;
}
}
}
//cerr << opt[l][r][2] << " ";
}
//cerr << "\n";
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3664kb
input:
10 ?>? >?< ??<? ?><?< ?????? >?<?<>?<?< ?><???><>< ??>>><><?? <>>?>>?>?> <?<>>??<?>
output:
2 2 3 4 5 8 7 8 5 6
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 352ms
memory: 3664kb
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: 318ms
memory: 3824kb
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: -100
Time Limit Exceeded
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 ...