oj.uz

Submission #236108

# Submission time Handle Problem Language Result Execution time Memory
236108 2020-05-31T08:31:23 Z VEGAnn Retro (COCI17_retro) C++14
5 / 100
 500 ms 15248 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][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];

    assert(sz(ans) > 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 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 18 ms 6528 KB Output isn't correct
8 Incorrect 15 ms 6400 KB Output isn't correct
9 Incorrect 24 ms 6528 KB Output isn't correct
10 Incorrect 27 ms 6528 KB Output isn't correct
11 Execution timed out 639 ms 12408 KB Time limit exceeded
12 Execution timed out 552 ms 11896 KB Time limit exceeded
13 Incorrect 282 ms 8952 KB Output isn't correct
14 Incorrect 251 ms 8824 KB Output isn't correct
15 Execution timed out 900 ms 14524 KB Time limit exceeded
16 Execution timed out 735 ms 13432 KB Time limit exceeded
17 Execution timed out 662 ms 12664 KB Time limit exceeded
18 Execution timed out 544 ms 11384 KB Time limit exceeded
19 Execution timed out 892 ms 15248 KB Time limit exceeded
20 Execution timed out 745 ms 13228 KB Time limit exceeded