Submission #473058

#TimeUsernameProblemLanguageResultExecution timeMemory
473058ntabc05101Dango Maker (JOI18_dango_maker)C++14
100 / 100
198 ms19056 KiB
#include <bits/stdc++.h>
using namespace std;

const int mxN = 3e3;
int n, m, dp[mxN + 1][3], res;
string a[mxN];

bool e(int i, int j, char c) {
  return i >= 0 && i < n && j >= 0 && j < m && a[i][j] == c;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i <= n + m - 4; i++) {
    int mxj = min(m, i + 2);
    for (int j = 0; j < mxj; ++j) {
      dp[j + 1][0] = max(dp[j][0], max(dp[j][1], dp[j][2]));
      dp[j + 1][1] = e(i + 1 - j, j - 1, 'R') && e(i + 1 - j, j, 'G') && e(i + 1 - j, j + 1, 'W') ? max(dp[j][0], dp[j][1]) + 1 : 0;
      dp[j + 1][2] = e(i - j, j, 'R') && e(i + 1 - j, j, 'G') && e(i + 2 - j, j, 'W') ? max(dp[j][0], dp[j][2]) + 1 : 0;
    }
    res += max(dp[mxj][0], max(dp[mxj][1], dp[mxj][2]));
  }

  cout << res << endl;

  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...