Submission #694067

#	Time	Username	Problem	Language	Result	Execution time	Memory
694067		rainboy	Sandwich (JOI16_sandwich)	C11	0 / 100	27 ms	13088 KiB

sandwich

#include <stdio.h>
#include <string.h>

#define N	50
#define M	50
#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 nzl[N][M], nzr[N][M], znl[N][M], znr[N][M], nzu[N][M], nzd[N][M], znu[N][M], znd[N][M], uul[N][M], uur[N][M], dp[N][M][N][M], ans[N][M];
	int n, m, r, i, i1, i2, j, j1, j2, x, tmp;

	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 (r = 0; r < 2; r++) {
		for (i = 0; i < n; i++) {
			nzl[i][0] = -1;
			for (j = 1; j < m; j++)
				nzl[i][j] = cc[i][j - 1] == 'N' && cc[i][j] == 'Z' ? j - 1 : nzl[i][j - 1];
			nzr[i][m - 1] = m;
			for (j = m - 2; j >= 0; j--)
				nzr[i][j] = cc[i][j] == 'N' && cc[i][j + 1] == 'Z' ? j + 1 : nzr[i][j + 1];
			znl[i][0] = -1;
			for (j = 1; j < m; j++)
				znl[i][j] = cc[i][j - 1] == 'Z' && cc[i][j] == 'N' ? j - 1 : znl[i][j - 1];
			znr[i][m - 1] = m;
			for (j = m - 2; j >= 0; j--)
				znr[i][j] = cc[i][j] == 'Z' && cc[i][j + 1] == 'N' ? j + 1 : znr[i][j + 1];
		}
		for (j = 0; j < m; j++) {
			nzu[0][j] = -1;
			for (i = 1; i < n; i++)
				nzu[i][j] = cc[i - 1][j] == 'N' && cc[i][j] == 'Z' ? i - 1 : nzu[i - 1][j];
			nzd[n - 1][j] = n;
			for (i = n - 2; i >= 0; i--)
				nzd[i][j] = cc[i][j] == 'N' && cc[i + 1][j] == 'Z' ? i + 1 : nzd[i + 1][j];
			znu[0][j] = -1;
			for (i = 1; i < n; i++)
				znu[i][j] = cc[i - 1][j] == 'Z' && cc[i][j] == 'N' ? i - 1 : znu[i - 1][j];
			znd[n - 1][j] = n;
			for (i = n - 2; i >= 0; i--)
				znd[i][j] = cc[i][j] == 'Z' && cc[i + 1][j] == 'N' ? i + 1 : znd[i + 1][j];
		}
		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]) {
							if (i1 < i2 && nzr[i1][j1] > j2)
								dp[i1 + 1][i2][j1][j2] = 1;
							if (i2 > i1 && znr[i2][j1] > j2)
								dp[i1][i2 - 1][j1][j2] = 1;
							if (j1 < j2 && nzd[i1][j1] > i2)
								dp[i1][i2][j1 + 1][j2] = 1;
							if (j2 > j1 && znd[i1][j2] > i2)
								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] = -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));
						}
		for (i1 = 0; i1 < n; i1++)
			for (i2 = i1; i2 < n; i2++) {
				x = -INF;
				for (j = 0; j < m; j++) {
					if (cc[i1][j] == 'N' || znd[i1][j] <= i2)
						x = -INF;
					else if (uul[i1][j] != -INF)
						x = max(x, uul[i1][j] + (j - 1) * (i2 - i1 + 1));
					if (cc[i2][j] == 'Z' && x != -INF)
						ans[i2][j] = max(ans[i2][j], x - j * (i2 - i1 + 1));
				}
				x = -INF;
				for (j = m - 1; j >= 0; j--) {
					if (cc[i1][j] == 'Z' || nzd[i1][j] <= i2)
						x = -INF;
					else if (uur[i1][j] != -INF)
						x = max(x, uur[i1][j] - (j + 1) * (i2 - i1 + 1));
					if (cc[i2][j] == 'N' && x != -INF)
						ans[i2][j] = max(ans[i2][j], x + j * (i2 - i1 + 1));
				}
			}
		for (i = 0; i < n; i++) {
			for (j1 = 0, j2 = m - 1; j1 < j2; j1++, j2--)
				tmp = ans[i][j1], ans[i][j1] = ans[i][j2], ans[i][j2] = tmp;
			for (j1 = 0, j2 = m - 1; j1 < j2; j1++, j2--)
				tmp = cc[i][j1], cc[i][j1] = cc[i][j2], cc[i][j2] = tmp;
		}
		for (j = 0; j < m; j++) {
			for (i1 = 0, i2 = n - 1; i1 < i2; i1++, i2--)
				tmp = ans[i1][j], ans[i1][j] = ans[i2][j], ans[i2][j] = tmp;
			for (i1 = 0, i2 = n - 1; i1 < i2; i1++, i2--)
				tmp = cc[i1][j], cc[i1][j] = cc[i2][j], cc[i2][j] = tmp;
		}
	}
	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 (stderr)

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
• Subtask 2: 0 / 65