SRM407 Div2 Medium

500

メモ化

const int N = 50 + 1;
bool g[N][N];

lli memo[N];

lli rec(int n)
{
  lli &ret = memo[n];
  if (ret != -1) return ret;

  lli sum = 0;

  for (int i = 0; i < (int)N; ++i) {
    if (g[n][i]) sum += rec(i);
  }

  return ret = max(1LL, sum);
}

class CorporationSalary {
public:
  long long totalSalary(vector <string> R)
  {
    const int size = R.size();

    fill(&g[0][0], &g[N - 1][N], false);

    for (int i = 0; i < (int)size; ++i) {
      for (int j = 0; j < (int)size; ++j) {
        g[i][j] = R[i][j] == 'Y';
      }
    }

    fill(memo, memo + N, -1);

    lli sum = 0;
    for (int i = 0; i < (int)size; ++i) {
      sum += rec(i);
    }
    return sum;
  }
};