Submission #648408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648408	2022-10-06T10:58:52 Z	bebra	Retro (COCI17_retro)	C++17	50 / 100	26 ms	27260 KB

retro

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

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

const int INF = 1e9;
const int MAX_N = 100 + 1;
const int MAX_BALANCE = MAX_N / 2 + 5;
char grid[MAX_N][MAX_N];

struct State {
    int len;
    // 0 - open, 1 - close
    bitset<MAX_N> sequence;

    State(int _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	7 ms	13396 KB	Output is correct
2	Correct	6 ms	13504 KB	Output is correct
3	Correct	7 ms	13396 KB	Output is correct
4	Correct	7 ms	13396 KB	Output is correct
5	Correct	8 ms	13500 KB	Output is correct
6	Correct	10 ms	13488 KB	Output is correct
7	Correct	14 ms	13396 KB	Output is correct
8	Correct	9 ms	13396 KB	Output is correct
9	Correct	12 ms	13468 KB	Output is correct
10	Correct	14 ms	13492 KB	Output is correct
11	Runtime error	17 ms	27252 KB	Execution killed with signal 11
12	Runtime error	19 ms	27220 KB	Execution killed with signal 11
13	Runtime error	18 ms	27204 KB	Execution killed with signal 11
14	Runtime error	17 ms	27212 KB	Execution killed with signal 11
15	Runtime error	18 ms	27220 KB	Execution killed with signal 11
16	Runtime error	23 ms	27248 KB	Execution killed with signal 11
17	Runtime error	19 ms	27200 KB	Execution killed with signal 11
18	Runtime error	18 ms	27228 KB	Execution killed with signal 11
19	Runtime error	26 ms	27260 KB	Execution killed with signal 11
20	Runtime error	18 ms	27228 KB	Execution killed with signal 11