Submission #239767

#	Time	Username	Problem	Language	Result	Execution time	Memory
239767		NONAME	Retro (COCI17_retro)	C++14	76 / 100	174 ms	115704 KiB

retro

#include <iostream>
#include <vector>
#include <set>
#include <array>
#include <queue>
using namespace std;

typedef long long ll;
typedef long double ld;
const int N = 3e2 + 10;
const int base = 1e9 + 7;

vector <array <int, 3> > vc[2], v;
queue <array <int, 3> > q;
char c[N][N];
int f[N][N][N], ans = 0, n, m;
bool mrk[N][N][N], was[N][N][N];

void check(int i, int j, int k, int ni, int nj) {
    if (c[ni][nj] == '*')
        return;

    if (c[ni][nj] == '.') {
        if (mrk[ni][nj][k] && f[i][j][k] == f[ni][nj][k] && !was[ni][nj][k]) {
            was[ni][nj][k] = 1;
            q.push({ni, nj, k});
        }
    } else if (c[ni][nj] == '(') {
        if (mrk[ni][nj][k + 1] && f[i][j][k] + 1 == f[ni][nj][k + 1] && !was[ni][nj][k]) {
            was[ni][nj][k + 1] = 1;
            q.push({ni, nj, k + 1});
        }
    } else {
        if (k > 0 && mrk[ni][nj][k - 1] && f[i][j][k] + 1 == f[ni][nj][k - 1] && !was[ni][nj][k - 1]) {
            was[ni][nj][k - 1] = 1;
            q.push({ni, nj, k - 1});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
        cin >> c[n - 1 - i][j];

    for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
    for (int k = 0; k <= i; ++k)
        f[i][j][k] = -1;

    for (int j = 0; j < m; ++j)
        if (c[0][j] == 'M') {
            f[0][j][0] = 0;
            v.push_back({0, j, 0});
        }

    for (int i = 0; i < n - 1; ++i)
    for (int j = 0; j < m; ++j)
    for (int k = 0; k <= i; ++k) {
        if (f[i][j][k] < 0)
            continue;

        for (int s = -1; s < 2; ++s) {
            int ni = i + 1, nj = j + s;
            if (ni < 0 || nj >= m)
                continue;

            if (c[ni][nj] == '*') {
                if (k == 0)
                    ans = max(ans, f[i][j][k]);
            } else if (c[ni][nj] == '.') f[ni][nj][k] = max(f[ni][nj][k], f[i][j][k]); else
                if (c[ni][nj] == '(') f[ni][nj][k + 1] = max(f[ni][nj][k + 1], f[i][j][k] + 1); else
                if (c[ni][nj] == ')') f[ni][nj][k - 1] = max(f[ni][nj][k - 1], f[i][j][k] + 1);
        }
    }

    for (int j = 0; j < m; ++j)
        ans = max(ans, f[n - 1][j][0]);

    cout << ans << "\n";

    for (int j = 0; j < m; ++j)
        if (f[n - 1][j][0] == ans)
            mrk[n - 1][j][0] = 1;

    for (int i = n - 2; i >= 0; --i)
    for (int j = 0; j < m; ++j)
    for (int k = 0; k <= i; ++k) {
        if (f[i][j][k] < 0)
            continue;

        for (int s = -1; s < 2 && !mrk[i][j][k]; ++s) {
            int ni = i + 1, nj = j + s;
            if (nj < 0 || nj >= m)
                continue;

            if (c[ni][nj] == '*') {
                if (k == 0 && ans == f[i][j][k])
                    mrk[i][j][k] = 1;
            } else if (c[ni][nj] == '.') {
                if (mrk[ni][nj][k] && f[i][j][k] == f[ni][nj][k])
                        mrk[i][j][k] = 1;
            } else if (c[ni][nj] == '(') {
                if (mrk[ni][nj][k + 1] && f[i][j][k] + 1 == f[ni][nj][k + 1])
                    mrk[i][j][k] = 1;
            } else {
                if (k > 0 && mrk[ni][nj][k - 1] && f[i][j][k] + 1 == f[ni][nj][k - 1])
                    mrk[i][j][k] = 1;
            }
        }
    }

    while (ans--) {
        vc[0].clear();
        vc[1].clear();

        for (auto st : v) {
            int i = st[0], j = st[1], k = st[2];

            for (int s = -1; s < 2; ++s) {
                int ni = i + 1, nj = j + s;
                if (nj == -1 || nj == m)
                    continue;

                if (c[ni][nj] == '*')
                    continue;

                check(i, j, k, ni, nj);
            }
        }

        while (!q.empty()) {
            auto cr = q.front();
            q.pop();

            int i = cr[0], j = cr[1], k = cr[2];
            if (c[i][j] == '(') {
                vc[0].push_back({i, j, k});
                continue;
            }

            if (c[i][j] == ')') {
                vc[1].push_back({i, j, k});
                continue;
            }

            for (int s = -1; s < 3; ++s) {
                int ni = i + 1, nj = j + s;

                if (nj == -1 || nj == m)
                    continue;

                if (c[ni][nj] == '*')
                    continue;

                check(i, j, k, ni, nj);
            }
        }

        if (!vc[0].empty()) {
            cout << "(";
            v = vc[0];
        } else {
            cout << ")";
            v = vc[1];
        }
    }
}

• Subtask 1: 76 / 100