Submission #648410

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648410	2022-10-06T11:01:48 Z	bebra	Retro (COCI17_retro)	C++17	50 / 100	440 ms	524288 KB

retro

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;

const short INF = 30000;
const int MAX_N = 250;
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[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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	144 ms	308408 KB	Output is correct
2	Correct	119 ms	308404 KB	Output is correct
3	Correct	122 ms	308404 KB	Output is correct
4	Correct	137 ms	308460 KB	Output is correct
5	Correct	118 ms	308488 KB	Output is correct
6	Correct	123 ms	308524 KB	Output is correct
7	Correct	129 ms	308632 KB	Output is correct
8	Correct	131 ms	308496 KB	Output is correct
9	Correct	128 ms	308504 KB	Output is correct
10	Correct	132 ms	308492 KB	Output is correct
11	Runtime error	440 ms	524288 KB	Execution killed with signal 11
12	Runtime error	382 ms	524288 KB	Execution killed with signal 11
13	Runtime error	398 ms	524288 KB	Execution killed with signal 11
14	Runtime error	414 ms	524288 KB	Execution killed with signal 11
15	Runtime error	386 ms	524288 KB	Execution killed with signal 11
16	Runtime error	392 ms	524288 KB	Execution killed with signal 11
17	Runtime error	431 ms	524288 KB	Execution killed with signal 11
18	Runtime error	389 ms	524288 KB	Execution killed with signal 11
19	Runtime error	411 ms	524288 KB	Execution killed with signal 11
20	Runtime error	385 ms	524288 KB	Execution killed with signal 11