oj.uz

Submission #236122

# Submission time Handle Problem Language Result Execution time Memory
236122 2020-05-31T08:55:36 Z VEGAnn Retro (COCI17_retro) C++14
5 / 100
 500 ms 15300 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][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 (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 (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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6400 KB Output is correct
2 Incorrect 8 ms 6400 KB Output isn't correct
3 Incorrect 8 ms 6400 KB Output isn't correct
4 Incorrect 8 ms 6272 KB Output isn't correct
5 Incorrect 9 ms 6400 KB Output isn't correct
6 Incorrect 16 ms 6400 KB Output isn't correct
7 Incorrect 19 ms 6656 KB Output isn't correct
8 Incorrect 15 ms 6400 KB Output isn't correct
9 Incorrect 25 ms 6528 KB Output isn't correct
10 Incorrect 28 ms 6528 KB Output isn't correct
11 Execution timed out 691 ms 12384 KB Time limit exceeded
12 Execution timed out 597 ms 12152 KB Time limit exceeded
13 Incorrect 299 ms 8952 KB Output isn't correct
14 Incorrect 262 ms 8952 KB Output isn't correct
15 Execution timed out 904 ms 14584 KB Time limit exceeded
16 Execution timed out 725 ms 13304 KB Time limit exceeded
17 Execution timed out 665 ms 12536 KB Time limit exceeded
18 Execution timed out 554 ms 11512 KB Time limit exceeded
19 Execution timed out 898 ms 15300 KB Time limit exceeded
20 Execution timed out 723 ms 13196 KB Time limit exceeded