oj.uz

Submission #239773

# Submission time Handle Problem Language Result Execution time Memory
239773 2020-06-17T09:28:34 Z NONAME Retro (COCI17_retro) C++14
100 / 100
 160 ms 115776 KB 
#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 sm, int ni, int nj) {
    if (c[ni][nj] == '*')
        return;

    if (c[ni][nj] == '.') {
        if (mrk[ni][nj][sm] && f[i][j][sm] == f[ni][nj][sm] && !was[ni][nj][sm]) {
            was[ni][nj][sm] = 1;
            q.push({ni, nj, sm});
        }
    } else if (c[ni][nj] == '(') {
        if (mrk[ni][nj][sm + 1] && f[i][j][sm] + 1 == f[ni][nj][sm + 1] && !was[ni][nj][sm + 1]) {
            was[ni][nj][sm + 1] = 1;
            q.push({ni, nj, sm + 1});
        }
    } else {
        if (sm > 0 && mrk[ni][nj][sm - 1] && f[i][j][sm] + 1 == f[ni][nj][sm - 1] && !was[ni][nj][sm - 1]) {
            was[ni][nj][sm - 1] = 1;
            q.push({ni, nj, sm - 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 sm = 0; sm <= i; ++sm)
        f[i][j][sm] = -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 sm = 0; sm <= i; ++sm) {
        if (f[i][j][sm] < 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 (sm == 0)
                    ans = max(ans, f[i][j][sm]);
            } else if (c[ni][nj] == '.') f[ni][nj][sm] = max(f[ni][nj][sm], f[i][j][sm]); else
                if (c[ni][nj] == '(') f[ni][nj][sm + 1] = max(f[ni][nj][sm + 1], f[i][j][sm] + 1); else
                if (sm > 0) f[ni][nj][sm - 1] = max(f[ni][nj][sm - 1], f[i][j][sm] + 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 sm = 0; sm <= i; ++sm) {
        if (f[i][j][sm] < 0)
            continue;

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

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

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

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

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

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

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

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

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

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

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

                if (nj < 0 || nj >= m)
                    continue;

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

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

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

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 2304 KB Output is correct
6 Correct 10 ms 7040 KB Output is correct
7 Correct 11 ms 10240 KB Output is correct
8 Correct 9 ms 5888 KB Output is correct
9 Correct 13 ms 10624 KB Output is correct
10 Correct 22 ms 13952 KB Output is correct
11 Correct 137 ms 108024 KB Output is correct
12 Correct 137 ms 106360 KB Output is correct
13 Correct 71 ms 50872 KB Output is correct
14 Correct 68 ms 48888 KB Output is correct
15 Correct 160 ms 115476 KB Output is correct
16 Correct 149 ms 113784 KB Output is correct
17 Correct 136 ms 97912 KB Output is correct
18 Correct 128 ms 95660 KB Output is correct
19 Correct 159 ms 113564 KB Output is correct
20 Correct 147 ms 115776 KB Output is correct