oj.uz

Submission #694091

# Submission time Handle Problem Language Result Execution time Memory
694091 2023-02-03T18:36:44 Z rainboy Sandwich (JOI16_sandwich) C
0 / 100
 121 ms 13524 KB 
#include <stdio.h>
#include <string.h>

#define N	51
#define M	51
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int main() {
	static char cc[N][M + 1];
	static int uul[N][M], uur[N][M], ddl[N][M], ddr[N][M], dp[N][M][N][M], ans[N][M];
	int n, m, i, i1, i2, j, j1, j2;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (i = 0; i < n; i++)
		memset(ans[i], -1, m * sizeof *ans[i]);
	for (i1 = 0; i1 < n; i1++)
		for (i2 = n - 1; i2 >= i1; i2--)
			for (j1 = 0; j1 < m; j1++)
				memset(dp[i1][i2][j1], 0, m * sizeof *dp[i1][i2][j1]);
	dp[0][n - 1][0][m - 1] = 1;
	for (i1 = 0; i1 < n; i1++)
		for (i2 = n - 1; i2 >= i1; i2--)
			for (j1 = 0; j1 < m; j1++)
				for (j2 = m - 1; j2 >= j1; j2--)
					if (dp[i1][i2][j1][j2]) {
						int good;

						good = 1;
						for (j = j1; j < j2; j++)
							if (cc[i1][j] == 'N' && cc[i1][j + 1] == 'Z') {
								good = 0;
								break;
							}
						if (i1 < i2 && good)
							dp[i1 + 1][i2][j1][j2] = 1;
						good = 1;
						for (j = j1; j < j2; j++)
							if (cc[i2][j] == 'Z' && cc[i2][j + 1] == 'N') {
								good = 0;
								break;
							}
						if (i2 > i1 && good)
							dp[i1][i2 - 1][j1][j2] = 1;
						good = 1;
						for (i = i1; i < i2; i++)
							if (cc[i][j1] == 'N' && cc[i + 1][j1] == 'Z') {
								good = 0;
								break;
							}
						if (j1 < j2 && good)
							dp[i1][i2][j1 + 1][j2] = 1;
						good = 1;
						for (i = i1; i < i2; i++)
							if (cc[i][j2] == 'Z' && cc[i + 1][j2] == 'N') {
								good = 0;
								break;
							}
						if (j2 > j1 && good)
							dp[i1][i2][j1][j2 - 1] = 1;
					}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			uul[i][j] = uur[i][j] = ddl[i][j] = ddr[i][j] = -INF;
	for (i1 = 0; i1 < n; i1++)
		for (i2 = i1; i2 < n; i2++)
			for (j1 = 0; j1 < m; j1++)
				for (j2 = j1; j2 < m; j2++)
					if (dp[i1][i2][j1][j2]) {
						uul[i1][j1] = max(uul[i1][j1], (i2 - i1 + 1) * (j2 - j1 + 1));
						uur[i1][j2] = max(uur[i1][j2], (i2 - i1 + 1) * (j2 - j1 + 1));
						ddl[i2][j1] = max(ddl[i2][j1], (i2 - i1 + 1) * (j2 - j1 + 1));
						ddr[i2][j2] = max(ddr[i2][j2], (i2 - i1 + 1) * (j2 - j1 + 1));
					}
	for (i1 = 0; i1 < n; i1++)
		for (j1 = 0; j1 < m; j1++)
			for (i2 = i1; i2 < n; i2++)
				for (j2 = j1; j2 < m; j2++) {
					int bad;

					bad = 0;
					for (i = i1; i <= i2; i++)
						for (j = j1; j <= j2; j++)
							if (cc[i][j] == 'N') {
								bad = 1;
								goto out1;
							}
out1:
					if (!bad && uul[i1][j1] != -INF)
						ans[i2][j2] = max(ans[i2][j2], uul[i1][j1] - (i2 - i1 + 1) * (j2 - j1 + 1));
					if (!bad && ddr[i2][j2] != -INF)
						ans[i1][j1] = max(ans[i1][j1], ddr[i2][j2] - (i2 - i1 + 1) * (j2 - j1 + 1));
					bad = 0;
					for (i = i1; i <= i2; i++)
						for (j = j1; j <= j2; j++)
							if (cc[i][j] == 'Z') {
								bad = 1;
								goto out2;
							}
out2:
					if (!bad && uur[i1][j2] != -INF)
						ans[i2][j1] = max(ans[i2][j1], uur[i1][j2] - (i2 - i1 + 1) * (j2 - j1 + 1));
					if (!bad && ddl[i2][j1] != -INF)
						ans[i1][j2] = max(ans[i1][j2], ddl[i2][j1] - (i2 - i1 + 1) * (j2 - j1 + 1));
				}
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			ans[i][j] = ans[i][j] == -1 ? -1 : (n * m - ans[i][j]) * 2;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			printf("%d%c", ans[i][j], j + 1 < m ? ' ' : '\n');
	return 0;
}

Compilation message

sandwich.c: In function 'main':
sandwich.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
sandwich.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 5408 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 5664 KB Output is correct
6 Correct 16 ms 13524 KB Output is correct
7 Correct 89 ms 12940 KB Output is correct
8 Correct 121 ms 13516 KB Output is correct
9 Incorrect 75 ms 10916 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 5408 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 5664 KB Output is correct
6 Correct 16 ms 13524 KB Output is correct
7 Correct 89 ms 12940 KB Output is correct
8 Correct 121 ms 13516 KB Output is correct
9 Incorrect 75 ms 10916 KB Output isn't correct
10 Halted 0 ms 0 KB -