oj.uz

Submission #236125

# Submission time Handle Problem Language Result Execution time Memory
236125 2020-05-31T09:00:41 Z VEGAnn Retro (COCI17_retro) C++14
60 / 100
 500 ms 21956 KB 
#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

# Verdict Execution time Memory 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