Submission #236128

#	Time	Username	Problem	Language	Result	Execution time	Memory
236128		VEGAnn	Retro (COCI17_retro)	C++14	50 / 100	57 ms	7168 KiB

retro

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define a3 array<int, 3>
using namespace std;
const int N = 310;
const int oo = 2e9;
string ans = "", f[2][N][N], t;
char s[N][N];
int n, m, ff[2][N][N], an = 0;

bool better(string &nw, string &old){
    return (sz(nw) > sz(old) || (sz(nw) == sz(old) && nw < old));
}

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

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 >> s[n - 1 - i][j];

    if (n > 100) {
        for (int j = 0; j < m; j++)
            if (s[0][j] == 'M')
                ff[0][j][0] = 0;
            else ff[0][j][0] = -1;

        for (int i = 0, tp = 0; i < n - 1; i++, tp ^= 1){
            for (int j = 0; j < m; j++)
            for (int sm = 0; sm <= i + 1; sm++)
                ff[tp ^ 1][j][sm] = -1;

            for (int j = 0; j < m; j++)
            for (int sm = 0; sm <= i; sm++){
                if (ff[tp][j][sm] == -1) continue;

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

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

                    if (s[ni][nj] == '*'){
                        if (sm == 0){
                            an = max(an, ff[tp][j][sm]);
                        }
                    } else if (s[ni][nj] == '.'){
                        upd(ff[tp ^ 1][nj][sm], ff[tp][j][sm]);
                    } else if (s[ni][nj] == '('){
                        upd(ff[tp ^ 1][nj][sm + 1], ff[tp][j][sm] + 1);
                    } else if (s[ni][nj] == ')'){
                        if (sm == 0) continue;

                        upd(ff[tp ^ 1][nj][sm - 1], ff[tp][j][sm] + 1);
                    }
                }
            }
        }

        int tp = (n - 1) % 2;

        for (int j = 0; j < m; j++)
            upd(an, ff[tp][j][0]);

        cout << an << '\n';

        for (int i = 0; i < an; i++)
            cout << "(";
    } else {
        for (int j = 0; j < m; j++)
            if (s[0][j] == 'M')
                f[0][j][0] = "";
            else f[0][j][0] = ")";

        for (int i = 0, tp = 0; i < n - 1; i++, tp ^= 1){
            for (int j = 0; j < m; j++)
            for (int sm = 0; sm <= i + 1; sm++)
                f[tp ^ 1][j][sm] = ")";

            for (int j = 0; j < m; j++)
            for (int sm = 0; sm <= i; sm++){
                if (f[tp][j][sm] == ")") continue;

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

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

                    if (s[ni][nj] == '*'){
                        if (sm == 0){
                            if (better(f[tp][j][sm], ans))
                                ans = f[tp][j][sm];
                        }
                    } else if (s[ni][nj] == '.'){
                        if (f[tp ^ 1][nj][sm] == ")" || better(f[tp][j][sm], f[tp ^ 1][nj][sm]))
                            f[tp ^ 1][nj][sm] = f[tp][j][sm];
                    } else if (s[ni][nj] == '('){
                        t = f[tp][j][sm] + "(";

                        if (f[tp ^ 1][nj][sm + 1] == ")" || better(t, f[tp ^ 1][nj][sm + 1]))
                            f[tp ^ 1][nj][sm + 1] = t;
                    } else if (s[ni][nj] == ')'){
                        if (sm == 0) continue;

                        t = f[tp][j][sm] + ")";

    //                    cerr << t << '\n' << f[tp ^ 1][nj][sm - 1] << '\n';

                        if (f[tp ^ 1][nj][sm - 1] == ")" || better(t, f[tp ^ 1][nj][sm - 1]))
                            f[tp ^ 1][nj][sm - 1] = t;
                    }
                }
            }
        }

        int tp = (n - 1) % 2;

        for (int j = 0; j < m; j++)
            if (f[tp][j][0] != ")" && better(f[tp][j][0], ans))
                ans = f[tp][j][0];
    }

    cout << sz(ans) << '\n' << ans;

    return 0;
}

• Subtask 1: 50 / 100