oj.uz

Submission #236120

# Submission time Handle Problem Language Result Execution time Memory
236120 2020-05-31T08:47:41 Z VEGAnn Retro (COCI17_retro) C++14
5 / 100
 500 ms 15096 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 (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 7 ms 6400 KB Output isn't correct
3 Incorrect 8 ms 6400 KB Output isn't correct
4 Incorrect 8 ms 6400 KB Output isn't correct
5 Incorrect 8 ms 6400 KB Output isn't correct
6 Incorrect 15 ms 6400 KB Output isn't correct
7 Incorrect 18 ms 6432 KB Output isn't correct
8 Incorrect 15 ms 6520 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 661 ms 12256 KB Time limit exceeded
12 Execution timed out 586 ms 11896 KB Time limit exceeded
13 Incorrect 297 ms 8980 KB Output isn't correct
14 Incorrect 268 ms 8856 KB Output isn't correct
15 Execution timed out 952 ms 14688 KB Time limit exceeded
16 Execution timed out 773 ms 13432 KB Time limit exceeded
17 Execution timed out 689 ms 12664 KB Time limit exceeded
18 Execution timed out 592 ms 11384 KB Time limit exceeded
19 Execution timed out 924 ms 15096 KB Time limit exceeded
20 Execution timed out 741 ms 13176 KB Time limit exceeded