답안 #236095

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236095	2020-05-31T07:45:47 Z	NONAME	Retro (COCI17_retro)	C++17	49 / 100	142 ms	106104 KB

retro

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define ft first
#define sd second
#define pb push_back
#define ppb pop_back
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
using namespace std;

typedef long long ll;
typedef long double ld;

int n, m, f[300][300][300];
string s[300];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
		cin >> s[i];

	for (int i = 0; i < n - i - 1; i++)
		swap(s[i], s[n - i - 1]);

	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
	for (int k = 0; k < n; k++)
		f[i][j][k] = -1;

	for (int i = 0; i < m; i++)
		if (s[0][i] == 'M')
			f[0][i][0] = 0;

    if (n <= 100) {
		string fs[n][m][n];

		for (int i = 0; i < m; i++)
			if (s[0][i] == 'M')
				fs[0][i][0] = "";

		for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < m; j++) {
			if (s[i][j] == '*')
				continue;

			if (j - 1 >= 0 && s[i + 1][j - 1] != '*') {
				if (s[i + 1][j - 1] == '.') {
					for (int k = 0; k < n; k++)
						if (f[i][j][k] != -1) {
							if (f[i][j][k] > f[i + 1][j - 1][k]) {
								f[i + 1][j - 1][k] = f[i][j][k];
								fs[i + 1][j - 1][k] = fs[i][j][k];
							} else if (f[i][j][k] == f[i + 1][j - 1][k]) {
								fs[i + 1][j - 1][k] = min(fs[i + 1][j - 1][k], fs[i][j][k]);
							}
						}
				} else {
					if (s[i + 1][j - 1] == '(') {
						for (int k = 0; k < n - 1; k++)
							if (f[i][j][k] != -1) {
								if (f[i][j][k] + 1 > f[i + 1][j - 1][k + 1]) {
									f[i + 1][j - 1][k + 1] = f[i][j][k] + 1;
									fs[i + 1][j - 1][k + 1] = fs[i][j][k] + '(';
								} else if (f[i][j][k] + 1 == f[i + 1][j - 1][k + 1]) {
									fs[i + 1][j - 1][k + 1] = min(fs[i + 1][j - 1][k + 1], fs[i][j][k] + '(');
								}
							}
					} else {
						for (int k = 1; k < n; k++)
							if (f[i][j][k] != -1) {
								if (f[i][j][k] + 1 > f[i + 1][j - 1][k - 1]) {
									f[i + 1][j - 1][k - 1] = f[i][j][k] + 1;
									fs[i + 1][j - 1][k - 1] = fs[i][j][k] + ')';
								} else if (f[i][j][k] + 1 == f[i + 1][j - 1][k - 1]) {
									fs[i + 1][j - 1][k - 1] = min(fs[i + 1][j - 1][k - 1], fs[i][j][k] + ')');
								}
							}
					}
				}
			}
			if (s[i + 1][j] != '*') {
				if (s[i + 1][j] == '.') {
					for (int k = 0; k < n; k++)
						if (f[i][j][k] != -1) {
							if (f[i][j][k] > f[i + 1][j][k]) {
								f[i + 1][j][k] = f[i][j][k];
								fs[i + 1][j][k] = fs[i][j][k];
							} else if (f[i][j][k] == f[i + 1][j][k]) {
								fs[i + 1][j][k] = min(fs[i + 1][j][k], fs[i][j][k]);
							}
						}
				} else {
					if (s[i + 1][j] == '(') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1) {
								if (f[i][j][k] + 1 > f[i + 1][j][k + 1]) {
									f[i + 1][j][k + 1] = f[i][j][k] + 1;
									fs[i + 1][j][k + 1] = fs[i][j][k] + '(';
								} else if (f[i][j][k] + 1 == f[i + 1][j][k + 1]) {
									fs[i + 1][j][k + 1] = min(fs[i + 1][j][k + 1], fs[i][j][k] + '(');
								}
							}
					} else {
						for (int k = 1; k < n; k++)
							if (f[i][j][k] != -1) {
								if (f[i][j][k] + 1 > f[i + 1][j][k - 1]) {
									f[i + 1][j][k - 1] = f[i][j][k] + 1;
									fs[i + 1][j][k - 1] = fs[i][j][k] + ')';
								} else if (f[i][j][k] + 1 == f[i + 1][j][k - 1]) {
									fs[i + 1][j][k - 1] = min(fs[i + 1][j][k - 1], fs[i][j][k] + ')');
								}
							}
					}
				}
			}
			if (j + 1 < m && s[i + 1][j + 1] != '*') {
				if (s[i + 1][j + 1] == '.') {
					for (int k = 0; k < n; k++)
						if (f[i][j][k] != -1) {
							if (f[i][j][k] > f[i + 1][j + 1][k]) {
								f[i + 1][j + 1][k] = f[i][j][k];
								fs[i + 1][j + 1][k] = fs[i][j][k];
							} else if (f[i][j][k] == f[i + 1][j + 1][k]) {
								fs[i + 1][j + 1][k] = min(fs[i + 1][j + 1][k], fs[i][j][k]);
							}
						}
				} else {
					if (s[i + 1][j + 1] == '(') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1) {
								if (f[i][j][k] + 1 > f[i + 1][j + 1][k + 1]) {
									f[i + 1][j + 1][k + 1] = f[i][j][k] + 1;
									fs[i + 1][j + 1][k + 1] = fs[i][j][k] + '(';
								} else if (f[i][j][k] + 1 == f[i + 1][j + 1][k + 1]) {
									fs[i + 1][j + 1][k + 1] = min(fs[i + 1][j + 1][k + 1], fs[i][j][k] + '(');
								}
							}
					} else {
						for (int k = 1; k < n; k++)
							if (f[i][j][k] != -1) {
								if (f[i][j][k] + 1 > f[i + 1][j + 1][k - 1]) {
									f[i + 1][j + 1][k - 1] = f[i][j][k] + 1;
									fs[i + 1][j + 1][k - 1] = fs[i][j][k] + ')';
								} else if (f[i][j][k] + 1 == f[i + 1][j + 1][k - 1]) {
									fs[i + 1][j + 1][k - 1] = min(fs[i + 1][j + 1][k - 1], fs[i][j][k] + ')');
								}
							}
					}
				}
			}
		}

		int x = 0, y = 0;
		for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (f[i][j][0] > f[x][y][0])
				x = i, y = j;

		cout << f[x][y][0] << el << fs[x][y][0];

		return 0;
    }

	for (int i = 0; i < n - 1; i++)
	for (int j = 0; j < m; j++)
        if (i == 0) {
			if (s[i][j] == 'M') {
				f[i][j][0] = 0;
                if (j - 1 >= 0 && s[i + 1][j - 1] != '*') {
					if (s[i + 1][j - 1] == '.') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j - 1][k] = max(f[i + 1][j - 1][k], f[i][j][k]);
					} else {
						if (s[i + 1][j - 1] == '(') {
							for (int k = 0; k < n; k++)
								if (f[i][j][k] != -1)
									f[i + 1][j - 1][k + 1] = max(f[i + 1][j - 1][k + 1], f[i][j][k] + 1);
						} else {
                            for (int k = 1; k < n; k++)
								if (f[i][j][k] != -1)
									f[i + 1][j - 1][k - 1] = max(f[i + 1][j - 1][k - 1], f[i][j][k] + 1);
						}
					}
                }
                if (s[i + 1][j] != '*') {
					if (s[i + 1][j] == '.') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j][k] = max(f[i + 1][j][k], f[i][j][k]);
					} else {
						if (s[i + 1][j] == '(') {
							for (int k = 0; k < n; k++)
								if (f[i][j][k] != -1)
									f[i + 1][j][k + 1] = max(f[i + 1][j][k + 1], f[i][j][k] + 1);
						} else {
                            for (int k = 1; k < n; k++)
								if (f[i][j][k] != -1)
									f[i + 1][j][k - 1] = max(f[i + 1][j][k - 1], f[i][j][k] + 1);
						}
					}
                }
                if (j + 1 < m && s[i + 1][j + 1] != '*') {
					if (s[i + 1][j + 1] == '.') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j + 1][k] = max(f[i + 1][j + 1][k], f[i][j][k]);
					} else {
						if (s[i + 1][j + 1] == '(') {
							for (int k = 0; k < n; k++)
								if (f[i][j][k] != -1)
									f[i + 1][j + 1][k + 1] = max(f[i + 1][j + 1][k + 1], f[i][j][k] + 1);
						} else {
                            for (int k = 1; k < n; k++)
								if (f[i][j][k] != -1)
									f[i + 1][j + 1][k - 1] = max(f[i + 1][j + 1][k - 1], f[i][j][k] + 1);
						}
					}
                }
			}
        } else {
			if (j - 1 >= 0 && s[i + 1][j - 1] != '*') {
				if (s[i + 1][j - 1] == '.') {
					for (int k = 0; k < n; k++)
						if (f[i][j][k] != -1)
							f[i + 1][j - 1][k] = max(f[i + 1][j - 1][k], f[i][j][k]);
				} else {
					if (s[i + 1][j - 1] == '(') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j - 1][k + 1] = max(f[i + 1][j - 1][k + 1], f[i][j][k] + 1);
					} else {
						for (int k = 1; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j - 1][k - 1] = max(f[i + 1][j - 1][k - 1], f[i][j][k] + 1);
					}
				}
			}
			if (s[i + 1][j] != '*') {
				if (s[i + 1][j] == '.') {
					for (int k = 0; k < n; k++)
						if (f[i][j][k] != -1)
							f[i + 1][j][k] = max(f[i + 1][j][k], f[i][j][k]);
				} else {
					if (s[i + 1][j] == '(') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j][k + 1] = max(f[i + 1][j][k + 1], f[i][j][k] + 1);
					} else {
						for (int k = 1; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j][k - 1] = max(f[i + 1][j][k - 1], f[i][j][k] + 1);
					}
				}
			}
			if (j + 1 < m && s[i + 1][j + 1] != '*') {
				if (s[i + 1][j + 1] == '.') {
					for (int k = 0; k < n; k++)
						if (f[i][j][k] != -1)
							f[i + 1][j + 1][k] = max(f[i + 1][j + 1][k], f[i][j][k]);
				} else {
					if (s[i + 1][j + 1] == '(') {
						for (int k = 0; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j + 1][k + 1] = max(f[i + 1][j + 1][k + 1], f[i][j][k] + 1);
					} else {
						for (int k = 1; k < n; k++)
							if (f[i][j][k] != -1)
								f[i + 1][j + 1][k - 1] = max(f[i + 1][j + 1][k - 1], f[i][j][k] + 1);
					}
				}
			}
		}

    int mx = 0;
    for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
		mx = max(mx, f[i][j][0]);

	cout << mx << el;
	cout << "()";
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:284:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < n; i++)
     ^~~
retro.cpp:288:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  cout << mx << el;
  ^~~~

Subtask #1

49.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Partially correct	5 ms	512 KB	Partially correct
2	Correct	5 ms	768 KB	Output is correct
3	Partially correct	5 ms	640 KB	Partially correct
4	Partially correct	5 ms	1024 KB	Partially correct
5	Correct	6 ms	2816 KB	Output is correct
6	Correct	22 ms	17920 KB	Output is correct
7	Partially correct	29 ms	28792 KB	Partially correct
8	Partially correct	20 ms	16512 KB	Partially correct
9	Partially correct	42 ms	37368 KB	Partially correct
10	Partially correct	49 ms	49408 KB	Partially correct
11	Partially correct	126 ms	99448 KB	Partially correct
12	Partially correct	121 ms	99448 KB	Partially correct
13	Partially correct	62 ms	44416 KB	Partially correct
14	Partially correct	59 ms	44416 KB	Partially correct
15	Partially correct	139 ms	105848 KB	Partially correct
16	Partially correct	132 ms	105720 KB	Partially correct
17	Partially correct	136 ms	89848 KB	Partially correct
18	Partially correct	128 ms	89720 KB	Partially correct
19	Partially correct	142 ms	106104 KB	Partially correct
20	Partially correct	138 ms	106104 KB	Partially correct