Submission #648414

# Submission time Handle Problem Language Result Execution time Memory
648414 2022-10-06T11:11:32 Z bebra Retro (COCI17_retro) C++17
100 / 100
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