oj.uz

Submission #236119

# Submission time Handle Problem Language Result Execution time Memory
236119 2020-05-31T08:46:53 Z VEGAnn Retro (COCI17_retro) C++14
5 / 100
 500 ms 15016 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, s[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++)
        cin >> s[n - 1 - i];

    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] == ")" || 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] == ")" || 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 (f[tp ^ 1][nj][sm - 1] == ")" || 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 7 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 6400 KB Output isn't correct
5 Incorrect 8 ms 6400 KB Output isn't correct
6 Incorrect 16 ms 6400 KB Output isn't correct
7 Incorrect 20 ms 6528 KB Output isn't correct
8 Incorrect 15 ms 6400 KB Output isn't correct
9 Incorrect 25 ms 6560 KB Output isn't correct
10 Incorrect 28 ms 6528 KB Output isn't correct
11 Execution timed out 704 ms 12348 KB Time limit exceeded
12 Execution timed out 612 ms 11976 KB Time limit exceeded
13 Incorrect 298 ms 9080 KB Output isn't correct
14 Incorrect 264 ms 8824 KB Output isn't correct
15 Execution timed out 941 ms 14600 KB Time limit exceeded
16 Execution timed out 745 ms 13432 KB Time limit exceeded
17 Execution timed out 687 ms 12536 KB Time limit exceeded
18 Execution timed out 585 ms 11496 KB Time limit exceeded
19 Execution timed out 939 ms 15016 KB Time limit exceeded
20 Execution timed out 776 ms 13120 KB Time limit exceeded