Submission #648400

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
648400	2022-10-06T10:35:00 Z	bebra	Retro (COCI17_retro)	C++17	46 / 100	184 ms	217868 KB

retro

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

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

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

int dp[MAX_N][MAX_N][MAX_BALANCE];
tuple<int, int, int> p[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];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k < MAX_BALANCE; ++k) {
                dp[i][j][k] = -INF;
            }
        }
    }
    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] = 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) {
                    if (grid[i][j] == '.' || grid[i][j] == '*') {
                        if (dp[prev_i][prev_j][k] > dp[i][j][k]) {
                            dp[i][j][k] = dp[prev_i][prev_j][k];
                            p[i][j][k] = {prev_i, prev_j, k};
                        }
                    } else if (grid[i][j] == '(') {
                        if (k != 0 && dp[prev_i][prev_j][k - 1] + 1 > dp[i][j][k]) {
                            dp[i][j][k] = dp[prev_i][prev_j][k - 1] + 1;
                            p[i][j][k] = {prev_i, prev_j, k - 1};
                        }
                    } else if (grid[i][j] == ')') {
                        if (k + 1 < max_balance && dp[prev_i][prev_j][k + 1] + 1 > dp[i][j][k]) {
                            dp[i][j][k] = dp[prev_i][prev_j][k + 1] + 1;
                            p[i][j][k] = {prev_i, prev_j, k + 1};
                        }
                    }
                }
            }
        }
    }
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == 0 || grid[i][j] == '*') {
                max_len = max(max_len, dp[i][j][0]);
            }
        }
    }
    string min_seq = "~";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if ((i == 0 || grid[i][j] == '*') && dp[i][j][0] == max_len) {
                string curr_seq;
                int curr_i = i;
                int curr_j = j;
                int curr_balance = 0;
                while (curr_i != n - 1) {
                    if (grid[curr_i][curr_j] == '(') {
                        curr_seq += '(';
                    } else if (grid[curr_i][curr_j] == ')') {
                        curr_seq += ')';
                    }
                    tie(curr_i, curr_j, curr_balance) = p[curr_i][curr_j][curr_balance];
                }
                reverse(curr_seq.begin(), curr_seq.end());
                min_seq = min(min_seq, curr_seq);
            }
        }
    }
    if (min_seq == "~") {
        min_seq = "";
    }
    cout << max_len << '\n';
    cout << min_seq << '\n';
    return 0;
}

Subtask #1

46.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	1 ms	468 KB	Partially correct
2	Correct	1 ms	968 KB	Output is correct
3	Partially correct	1 ms	724 KB	Partially correct
4	Partially correct	1 ms	1224 KB	Partially correct
5	Correct	2 ms	3668 KB	Output is correct
6	Partially correct	8 ms	11860 KB	Partially correct
7	Partially correct	11 ms	17740 KB	Partially correct
8	Partially correct	6 ms	8788 KB	Partially correct
9	Partially correct	12 ms	18248 KB	Partially correct
10	Partially correct	15 ms	24916 KB	Partially correct
11	Partially correct	167 ms	203752 KB	Partially correct
12	Partially correct	160 ms	203816 KB	Partially correct
13	Partially correct	77 ms	90632 KB	Partially correct
14	Partially correct	71 ms	90572 KB	Partially correct
15	Partially correct	181 ms	217060 KB	Partially correct
16	Partially correct	173 ms	216972 KB	Partially correct
17	Partially correct	154 ms	184008 KB	Partially correct
18	Partially correct	145 ms	183796 KB	Partially correct
19	Partially correct	184 ms	217868 KB	Partially correct
20	Partially correct	171 ms	217632 KB	Partially correct