oj.uz

Submission #236117

# Submission time Handle Problem Language Result Execution time Memory
236117 2020-05-31T08:40:26 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, 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;

            if (sm == 0 && better(f[tp][j][sm], ans))
                ans = f[tp][j][sm];

            for (int stp = -1; stp < 2; stp++){
                int ni = i + 1, nj = j + stp;

                if (nj < 0 || nj >= m) continue;

                if (s[ni][nj] == '*'){
                } 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 10 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 6528 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 25 ms 6528 KB Output isn't correct
10 Incorrect 27 ms 6528 KB Output isn't correct
11 Execution timed out 661 ms 12408 KB Time limit exceeded
12 Execution timed out 598 ms 12024 KB Time limit exceeded
13 Incorrect 302 ms 8940 KB Output isn't correct
14 Incorrect 289 ms 8804 KB Output isn't correct
15 Execution timed out 947 ms 14524 KB Time limit exceeded
16 Execution timed out 782 ms 13460 KB Time limit exceeded
17 Execution timed out 671 ms 12536 KB Time limit exceeded
18 Execution timed out 544 ms 11512 KB Time limit exceeded
19 Execution timed out 939 ms 15096 KB Time limit exceeded
20 Execution timed out 763 ms 13184 KB Time limit exceeded