답안 #236171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236171	2020-05-31T10:41:53 Z	NONAME	Retro (COCI17_retro)	C++17	49 / 100	270 ms	320632 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];
pair <int, int> pr[300][300][300];
string s[N];

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, pr[i][j][k] = {-1, -1};

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

    for (int i = 0; i < n - 1; i++)
	for (int j = 0; j < m; j++) {
		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])
							pr[i + 1][j - 1][k] = {j, k};
						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) {
							if (f[i][j][k] + 1 >= f[i + 1][j - 1][k + 1])
								pr[i + 1][j - 1][k + 1] = {j, k};
							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) {
							if (f[i][j][k] + 1 > f[i + 1][j - 1][k - 1])
								pr[i + 1][j - 1][k  - 1] = {j, k};
							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) {
						if (f[i][j][k] > f[i + 1][j][k])
							pr[i + 1][j][k] = {j, k};
						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) {
							if (f[i][j][k] + 1 >= f[i + 1][j][k + 1])
								pr[i + 1][j][k + 1] = {j, k};
							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) {
							if (f[i][j][k] + 1 > f[i + 1][j][k - 1])
								pr[i + 1][j][k - 1] = {j, k};
							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) {
						if (f[i][j][k] > f[i + 1][j + 1][k])
							pr[i + 1][j + 1][k] = {j, k};
						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) {
							if (f[i][j][k] + 1 >= f[i + 1][j + 1][k + 1])
                                pr[i + 1][j + 1][k + 1] = {j, k};
							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) {
							if (f[i][j][k] + 1 > f[i + 1][j + 1][k - 1])
								pr[i + 1][j + 1][k - 1] = {j, k};
							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;

	vector <string> v;

	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++) {
		if (f[i][j][0] != mx)
			continue;

		int x = i, y = j, k = 0;
		string res = "";
        while (x != 0) {
        	int old_y = y;

			if (s[x][y] == '.') {
				y = pr[x][y][k].ft;
				k = pr[x][old_y][k].sd;
				x--;
				continue;
			}

			res += s[x][y];

			y = pr[x][y][k].ft;
			k = pr[x][old_y][k].sd;
			x--;
        }

        reverse(res.begin(), res.end());

        v.pb(res);
	}

	sort(v.begin(), v.end());

	cout << v[0];
}

Compilation message

retro.cpp: In function 'int main()':
retro.cpp:126:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i = 0; i < n; i++)
     ^~~
retro.cpp:130: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	6 ms	3840 KB	Partially correct
2	Correct	6 ms	4480 KB	Output is correct
3	Partially correct	6 ms	4096 KB	Partially correct
4	Partially correct	7 ms	4864 KB	Partially correct
5	Correct	9 ms	8832 KB	Output is correct
6	Correct	16 ms	20224 KB	Output is correct
7	Partially correct	21 ms	29056 KB	Partially correct
8	Partially correct	14 ms	15616 KB	Partially correct
9	Partially correct	22 ms	29568 KB	Partially correct
10	Partially correct	27 ms	39424 KB	Partially correct
11	Partially correct	235 ms	300692 KB	Partially correct
12	Partially correct	226 ms	300536 KB	Partially correct
13	Partially correct	115 ms	134448 KB	Partially correct
14	Partially correct	110 ms	134392 KB	Partially correct
15	Partially correct	258 ms	319592 KB	Partially correct
16	Partially correct	250 ms	319736 KB	Partially correct
17	Partially correct	213 ms	270204 KB	Partially correct
18	Partially correct	212 ms	270280 KB	Partially correct
19	Partially correct	270 ms	320632 KB	Partially correct
20	Partially correct	249 ms	320632 KB	Partially correct