Submission #236248

#	Time	Username	Problem	Language	Result	Execution time	Memory
236248		VEGAnn	Retro (COCI17_retro)	C++14	100 / 100	140 ms	61304 KiB

retro

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define a3 array<int, 3>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 310;
const int oo = 2e9;
vector<a3> vc, vec[2];
queue<a3> q;
char c[N][N];
short f[N][N][N], ans = 0, n, m;
bool mrk[N][N][N], was[N][N][N];

void upd(short &x, short y){
    x = max(x, y);
}

void check(int i, int j, int sm, int ni, int nj){
    if (c[ni][nj] == '*'){
        return;
    } else 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);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    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;
            vc.PB({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 stp = -1; stp < 2; stp++){
            int ni = i + 1, nj = j + stp;

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

            if (c[ni][nj] == '*'){
                if (sm == 0) {
                    upd(ans, f[i][j][sm]);
                }
            } else if (c[ni][nj] == '.'){
                upd(f[ni][nj][sm], f[i][j][sm]);
            } else if (c[ni][nj] == '('){
                upd(f[ni][nj][sm + 1], f[i][j][sm] + 1);
            } else if (sm > 0){
                upd(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 stp = -1; stp < 2 && !mrk[i][j][sm]; stp++){
                int ni = i + 1, nj = j + stp;

                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;
                }
            }
        }
    }

    for (int itr = 0; itr < ans; itr++){
        vec[0].clear();
        vec[1].clear();

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

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

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

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

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

        while (sz(q)){
            a3 cr = q.front(); q.pop();

            int i = cr[0], j = cr[1], sm = cr[2];

            if (c[i][j] == '('){
                vec[0].PB({i, j, sm});
                continue;
            }

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

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

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

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

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

        if (sz(vec[0]) > 0){
            cout << "(";

            vc = vec[0];
        } else {
            cout << ")";

            vc = vec[1];
        }
    }

    return 0;
}

• Subtask 1: 100 / 100