Submission #9631981 - AtCoder Grand Contest 004 | AtCoder
// ===================================
// author: M_sea
// website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
template <typename T>
inline void chkmax(T &x, T y)
{
if (y > x)
x = y;
}
inline int read()
{
int X = 0, w = 1;
char c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
w = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
X = X * 10 + c - '0', c = getchar();
return X * w;
}
const int N = 100 + 1;
int n, m;
char s[N][N];
short sum[N][N];
short dp[N][N][N][N];
inline short f(int lx, int ly, int rx, int ry)
{
if (lx > rx)
swap(lx, rx);
if (ly > ry)
swap(ly, ry);
return sum[rx][ry] - sum[lx - 1][ry] - sum[rx][ly - 1] + sum[lx - 1][ly - 1];
}
int main()
{
n = read(), m = read();
int x, y;
for (re int i = 1; i <= n; ++i)
{
scanf("%s", s[i] + 1);
for (re int j = 1; j <= m; ++j)
{
if (s[i][j] == 'E')
x = i, y = j;
if (s[i][j] == 'o')
sum[i][j] = 1;
}
}
for (re int i = 1; i <= n; ++i)
for (re int j = 1; j <= m; ++j)
sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
for (re int u = x; u; --u)
for (re int l = y; l; --l)
for (re int d = x; d <= n; ++d)
for (re int r = y; r <= m; ++r)
{
int U = d - x + 1, L = r - y + 1, D = n - x + u, R = m - y + l;
if (u > U)
chkmax(dp[u - 1][l][d][r],
(short)(dp[u][l][d][r] + f(u - 1, max(l, L), u - 1, min(r, R))));
if (l > L)
chkmax(dp[u][l - 1][d][r],
(short)(dp[u][l][d][r] + f(max(u, U), l - 1, min(d, D), l - 1)));
if (d < D)
chkmax(dp[u][l][d + 1][r],
(short)(dp[u][l][d][r] + f(d + 1, max(l, L), d + 1, min(r, R))));
if (r < R)
chkmax(dp[u][l][d][r + 1],
(short)(dp[u][l][d][r] + f(max(u, U), r + 1, min(d, D), r + 1)));
}
short ans = 0;
for (re int u = x; u; --u)
for (re int l = y; l; --l)
for (re int d = x; d <= n; ++d)
for (re int r = y; r <= m; ++r)
chkmax(ans, dp[u][l][d][r]);
printf("%d\n", ans);
return 0;
}
Submission
Task
E - Salvage Robots
User name
M_sea
Created time
2020/01/19 22:11:00
Language
C++14 (GCC 5.4.1)
Status
AC
Score
1400
Source length
2111 Byte
File name
Exec time
85 ms
Memory usage
201088 KB
评论
发表评论