Submission #473058

#	Time	Username	Problem	Language	Result	Execution time	Memory
473058		ntabc05101	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	198 ms	19056 KiB

dango_maker

#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;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67