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

retro

#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;
}

Subtask #1

100.0 / 100.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