Submission #648411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648411	2022-10-06T11:03:35 Z	bebra	Retro (COCI17_retro)	C++17	50 / 100	500 ms	430284 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	173 ms	430016 KB	Output is correct
2	Correct	167 ms	429988 KB	Output is correct
3	Correct	171 ms	429992 KB	Output is correct
4	Correct	190 ms	429992 KB	Output is correct
5	Correct	163 ms	430096 KB	Output is correct
6	Correct	174 ms	430100 KB	Output is correct
7	Correct	191 ms	430192 KB	Output is correct
8	Correct	171 ms	430008 KB	Output is correct
9	Correct	174 ms	430044 KB	Output is correct
10	Correct	177 ms	430040 KB	Output is correct
11	Execution timed out	514 ms	430168 KB	Time limit exceeded
12	Incorrect	412 ms	430220 KB	Output isn't correct
13	Incorrect	323 ms	430168 KB	Output isn't correct
14	Incorrect	278 ms	430156 KB	Output isn't correct
15	Execution timed out	510 ms	430108 KB	Time limit exceeded
16	Incorrect	461 ms	430284 KB	Output isn't correct
17	Incorrect	475 ms	430136 KB	Output isn't correct
18	Incorrect	416 ms	430276 KB	Output isn't correct
19	Execution timed out	515 ms	430192 KB	Time limit exceeded
20	Incorrect	470 ms	430140 KB	Output isn't correct