Submission #648411

#	Time	Username	Problem	Language	Result	Execution time	Memory
648411		bebra	Retro (COCI17_retro)	C++17	50 / 100	515 ms	430284 KiB

retro

#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 / 3 + 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[MAX_N][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 + 5;
    // 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, y - 1);
            }
        }
        if (y + 1 < m) {
            if (grid[x + 1][y + 1] != '*') {
                moves.emplace_back(x + 1, y + 1);
            }
        }
        if (grid[x + 1][y] != '*') {
            moves.emplace_back(x + 1, y);
        }
        return moves;
    };
    for (int j = 0; j < m; ++j) {
        if (grid[n - 1][j] == 'M') {
            dp[n - 1][j][0] = State(0);
        }
    }
    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) {
                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][j][k] = max(dp[i][j][k], new_state);
                }
            }
        }
    }
    State max_state;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0 || grid[i][j] == '*') {
                max_state = max(max_state, dp[i][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;
}

• Subtask 1: 50 / 100