oj.uz

Submission #239760

# Submission time Handle Problem Language Result Execution time Memory
239760 2020-06-17T09:05:30 Z NONAME Retro (COCI17_retro) C++14
46 / 100
 185 ms 132600 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 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 == -1 || 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 == -1 || 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
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Partially correct 5 ms 768 KB Partially correct
3 Partially correct 5 ms 768 KB Partially correct
4 Correct 5 ms 1024 KB Output is correct
5 Partially correct 6 ms 2432 KB Partially correct
6 Partially correct 10 ms 7936 KB Partially correct
7 Partially correct 12 ms 10624 KB Partially correct
8 Partially correct 9 ms 6272 KB Partially correct
9 Partially correct 14 ms 12032 KB Partially correct
10 Partially correct 18 ms 15744 KB Partially correct
11 Partially correct 159 ms 122488 KB Partially correct
12 Partially correct 152 ms 120568 KB Partially correct
13 Partially correct 79 ms 56824 KB Partially correct
14 Partially correct 75 ms 56440 KB Partially correct
15 Partially correct 179 ms 130528 KB Partially correct
16 Partially correct 169 ms 129016 KB Partially correct
17 Partially correct 154 ms 111608 KB Partially correct
18 Partially correct 139 ms 111352 KB Partially correct
19 Partially correct 185 ms 132600 KB Partially correct
20 Partially correct 165 ms 130552 KB Partially correct