oj.uz

Submission #236123

# Submission time Handle Problem Language Result Execution time Memory
236123 2020-05-31T08:59:25 Z VEGAnn Retro (COCI17_retro) C++14
20 / 100
 500 ms 21800 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 (better(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 (better(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 (better(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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6400 KB Integer 0 violates the range [1, 100000]
2 Correct 8 ms 6304 KB Output is correct
3 Correct 8 ms 6400 KB Output is correct
4 Incorrect 8 ms 6400 KB Integer 0 violates the range [1, 100000]
5 Correct 8 ms 6400 KB Output is correct
6 Incorrect 10 ms 6400 KB Integer 0 violates the range [1, 100000]
7 Incorrect 13 ms 6400 KB Integer 0 violates the range [1, 100000]
8 Incorrect 11 ms 6400 KB Integer 0 violates the range [1, 100000]
9 Incorrect 14 ms 6400 KB Integer 0 violates the range [1, 100000]
10 Incorrect 16 ms 6400 KB Integer 0 violates the range [1, 100000]
11 Incorrect 210 ms 6528 KB Integer 0 violates the range [1, 100000]
12 Execution timed out 746 ms 17960 KB Time limit exceeded
13 Correct 387 ms 11876 KB Output is correct
14 Incorrect 101 ms 6520 KB Integer 0 violates the range [1, 100000]
15 Incorrect 230 ms 6400 KB Integer 0 violates the range [1, 100000]
16 Incorrect 244 ms 6400 KB Integer 0 violates the range [1, 100000]
17 Incorrect 200 ms 6528 KB Integer 0 violates the range [1, 100000]
18 Incorrect 214 ms 6528 KB Integer 0 violates the range [1, 100000]
19 Execution timed out 1090 ms 21800 KB Time limit exceeded
20 Incorrect 232 ms 6648 KB Integer 0 violates the range [1, 100000]