#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 (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 (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 ", ans[i][j]);
printf("\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]);
| ^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5716 KB |
Output is correct |
| 6 |
Correct |
19 ms |
13080 KB |
Output is correct |
| 7 |
Correct |
19 ms |
12576 KB |
Output is correct |
| 8 |
Correct |
22 ms |
13012 KB |
Output is correct |
| 9 |
Incorrect |
16 ms |
10664 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
2 ms |
5460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5716 KB |
Output is correct |
| 6 |
Correct |
19 ms |
13080 KB |
Output is correct |
| 7 |
Correct |
19 ms |
12576 KB |
Output is correct |
| 8 |
Correct |
22 ms |
13012 KB |
Output is correct |
| 9 |
Incorrect |
16 ms |
10664 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
