# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
648414 |
2022-10-06T11:11:32 Z |
bebra |
Retro (COCI17_retro) |
C++17 |
|
342 ms |
4672 KB |
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << #x << ": " << x << endl;
const short INF = 30000;
const int MAX_N = 300 + 1;
const int MAX_BALANCE = MAX_N / 2 + 1;
char grid[MAX_N][MAX_N];
struct State {
short len;
// 0 - open, 1 - close
bitset<MAX_N> sequence;
State(short _len = -INF) : len(_len) {}
bool operator<(const State& other) const {
if (len == other.len) {
if (sequence == other.sequence) {
return false;
}
int lowest_bit = (sequence ^ other.sequence)._Find_first();
return sequence.test(lowest_bit);
} else {
return len < other.len;
}
}
};
State dp[2][MAX_N][MAX_BALANCE];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
for (int j = 0; j < m; ++j) {
grid[i][j] = s[j];
}
}
const int max_balance = n / 2 + 1;
// moves (if possible):
// (i - 1; j - 1)
// (i - 1; j)
// (i - 1; j + 1)
auto gen_moves = [&](int x, int y) -> vector<pair<int, int>> {
vector<pair<int, int>> moves;
if (y - 1 >= 0) {
if (grid[x + 1][y - 1] != '*') {
moves.emplace_back((x + 1) & 1, y - 1);
}
}
if (y + 1 < m) {
if (grid[x + 1][y + 1] != '*') {
moves.emplace_back((x + 1) & 1, y + 1);
}
}
if (grid[x + 1][y] != '*') {
moves.emplace_back((x + 1) & 1, y);
}
return moves;
};
for (int j = 0; j < m; ++j) {
if (grid[n - 1][j] == 'M') {
dp[(n - 1) & 1][j][0] = State(0);
}
}
State max_state;
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j < m; ++j) {
auto moves = gen_moves(i, j);
for (int k = 0; k < max_balance; ++k) {
dp[i & 1][j][k] = State();
for (const auto& [prev_i, prev_j] : moves) {
State new_state;
if (grid[i][j] == '.' || grid[i][j] == '*') {
new_state = dp[prev_i][prev_j][k];
} else if (grid[i][j] == '(' && k != 0) {
new_state = dp[prev_i][prev_j][k - 1];
if (new_state.len == -INF) continue;
++new_state.len;
} else if (grid[i][j] == ')' && k + 1 < max_balance) {
new_state = dp[prev_i][prev_j][k + 1];
if (new_state.len == -INF) continue;
new_state.sequence.set(new_state.len);
++new_state.len;
}
dp[i & 1][j][k] = max(dp[i & 1][j][k], new_state);
}
}
if (i == 0 || grid[i][j] == '*') {
max_state = max(max_state, dp[i & 1][j][0]);
}
}
}
cout << max_state.len << '\n';
for (int i = 0; i < max_state.len; ++i) {
if (max_state.sequence.test(i)) {
cout << ')';
} else {
cout << '(';
}
}
cout << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4564 KB |
Output is correct |
2 |
Correct |
3 ms |
4564 KB |
Output is correct |
3 |
Correct |
2 ms |
4564 KB |
Output is correct |
4 |
Correct |
2 ms |
4564 KB |
Output is correct |
5 |
Correct |
3 ms |
4564 KB |
Output is correct |
6 |
Correct |
7 ms |
4616 KB |
Output is correct |
7 |
Correct |
10 ms |
4564 KB |
Output is correct |
8 |
Correct |
6 ms |
4620 KB |
Output is correct |
9 |
Correct |
11 ms |
4628 KB |
Output is correct |
10 |
Correct |
14 ms |
4628 KB |
Output is correct |
11 |
Correct |
290 ms |
4664 KB |
Output is correct |
12 |
Correct |
259 ms |
4664 KB |
Output is correct |
13 |
Correct |
125 ms |
4664 KB |
Output is correct |
14 |
Correct |
115 ms |
4564 KB |
Output is correct |
15 |
Correct |
342 ms |
4664 KB |
Output is correct |
16 |
Correct |
294 ms |
4668 KB |
Output is correct |
17 |
Correct |
260 ms |
4672 KB |
Output is correct |
18 |
Correct |
292 ms |
4672 KB |
Output is correct |
19 |
Correct |
329 ms |
4668 KB |
Output is correct |
20 |
Correct |
305 ms |
4564 KB |
Output is correct |