提出 #1624944

---

ソースコード 拡げる

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1000000000000001LL;

int H, W;
string S[50];
int64 dp[55][55];
int64 dp2[55][55][55][55];

int64 rec2(int sy, int sx, int gy, int gx)
{
  return (dp2[sy][sx][gy][gx]);
}

int64 rec(int sy, int sx)
{
  if(sy >= H && sx >= W) return (-INF);
  if(~dp[sy][sx]) return (dp[sy][sx]);
  int64 ret = rec2(sy, sx, H - 1, W - 1);
  for(int i = sy; i < H; i++) {
    for(int j = sx; j < W; j++) {
      if((isdigit(S[i][j]))) {
        if(i + 2 < H && S[i + 1][j] == '+') {
          auto x = rec2(sy, sx, i, j);
          auto y = rec(i + 2, j);
          if(x >= 0 && y >= 0) ret = max(ret, x + y);
        }

        if(j + 2 < W && S[i][j + 1] == '+') {
          auto x = rec2(sy, sx, i, j);
          auto y = rec(i, j + 2);
          if(x >= 0 && y >= 0) ret = max(ret, x + y);
        }

        if((i + 1 < H && S[i + 1][j] == '+') &&
           (j + 1 < W && S[i][j + 1] == '+')) {
          if(i + 1 < H && j + 1 < W) {
            auto x = rec2(sy, sx, i, j);
            auto y = rec(i + 1, j + 1);
            if(x >= 0 && y >= 0) ret = max(ret, x + y);
          }
        }
      }
    }
  }
  return (dp[sy][sx] = min(INF, ret));
}

int main()
{
  memset(dp, -1, sizeof(dp));
  fill_n(***dp2, 55 * 55 * 55 * 55, -INF);

  cin >> H >> W;
  for(int i = 0; i < H; i++) cin >> S[i];


  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) {
      if(isdigit(S[i][j])) {
        dp2[i][j][i][j] = S[i][j] - '0';
        for(int m = i; m < H; m++) {
          for(int n = j; n < W; n++) {
            if(isdigit(S[m][n])) {
              if(dp2[i][j][m][n] >= 0) {
                if(m + 2 < H && S[m + 1][n] == '*') {
                  dp2[i][j][m + 2][n] = max(dp2[i][j][m + 2][n], dp2[i][j][m][n] * (int64) (S[m + 2][n] - '0'));
                  dp2[i][j][m + 2][n] = min(INF, dp2[i][j][m + 2][n]);
                }
                if(n + 2 < W && S[m][n + 1] == '*') {
                  dp2[i][j][m][n + 2] = max(dp2[i][j][m][n + 2], dp2[i][j][m][n] * (int64) (S[m][n + 2] - '0'));
                  dp2[i][j][m][n + 2] = min(INF, dp2[i][j][m][n + 2]);
                }
                if((n + 1 < W && S[m][n + 1] == '*') || (m + 1 < H && S[m + 1][n] == '*')) {
                  if(n + 1 < W && m + 1 < H) {
                    dp2[i][j][m + 1][n + 1] = max(dp2[i][j][m + 1][n + 1], dp2[i][j][m][n] * (int64) (S[m + 1][n + 1] - '0'));
                    dp2[i][j][m + 1][n + 1] = min(INF, dp2[i][j][m + 1][n + 1]);
                  }
                }
              }
            }
          }
        }
      }
    }
  }

  auto p = rec(0, 0);
  if(p >= INF)
    cout << -1 << endl;
  else
    cout << p << endl;
}

提出情報

ジャッジ結果