oj.uz

Submission #239770

# Submission time Handle Problem Language Result Execution time Memory
239770 2020-06-17T09:24:15 Z NONAME Retro (COCI17_retro) C++14
76 / 100
 179 ms 115832 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]) {
            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 < 3; ++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
76.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 5 ms 2304 KB Output is correct
6 Partially correct 10 ms 7040 KB Partially correct
7 Correct 11 ms 10240 KB Output is correct
8 Partially correct 9 ms 5888 KB Partially correct
9 Correct 15 ms 10624 KB Output is correct
10 Correct 15 ms 14080 KB Output is correct
11 Partially correct 141 ms 108024 KB Partially correct
12 Correct 137 ms 106360 KB Output is correct
13 Partially correct 69 ms 50808 KB Partially correct
14 Correct 66 ms 48888 KB Output is correct
15 Partially correct 158 ms 115560 KB Partially correct
16 Partially correct 146 ms 113936 KB Partially correct
17 Partially correct 131 ms 97912 KB Partially correct
18 Correct 122 ms 95608 KB Output is correct
19 Partially correct 179 ms 113528 KB Partially correct
20 Correct 152 ms 115832 KB Output is correct