답안 #236125

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236125	2020-05-31T09:00:41 Z	VEGAnn	Retro (COCI17_retro)	C++14	60 / 100	500 ms	21956 KB

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;

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

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

    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

60.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	6400 KB	Output is correct
2	Correct	8 ms	6400 KB	Output is correct
3	Correct	8 ms	6400 KB	Output is correct
4	Correct	8 ms	6400 KB	Output is correct
5	Correct	9 ms	6400 KB	Output is correct
6	Correct	19 ms	6656 KB	Output is correct
7	Correct	21 ms	6784 KB	Output is correct
8	Correct	17 ms	6528 KB	Output is correct
9	Correct	30 ms	6784 KB	Output is correct
10	Correct	33 ms	6912 KB	Output is correct
11	Execution timed out	963 ms	19388 KB	Time limit exceeded
12	Execution timed out	769 ms	18040 KB	Time limit exceeded
13	Correct	407 ms	12096 KB	Output is correct
14	Correct	333 ms	11640 KB	Output is correct
15	Execution timed out	1090 ms	21200 KB	Time limit exceeded
16	Execution timed out	1016 ms	20972 KB	Time limit exceeded
17	Execution timed out	1000 ms	19448 KB	Time limit exceeded
18	Execution timed out	778 ms	17136 KB	Time limit exceeded
19	Execution timed out	1098 ms	21956 KB	Time limit exceeded
20	Execution timed out	1000 ms	20984 KB	Time limit exceeded