Submission #1147163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147163		fryingduc	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	166 ms	9304 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 3005;
int n, m;
char a[maxn][maxn];
int f[maxn][3];

bool match_vertical(int r, int c) {
  if (c <= 2 || r < 1) return 0;
  return a[r][c - 2] == 'R' and a[r][c - 1] == 'G' and a[r][c] == 'W';
}

bool match_horizontal(int r, int c) {
  if (r <= 2 || c < 1) return 0;
  return a[r - 2][c] == 'R' and a[r - 1][c] == 'G' and a[r][c] == 'W';
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      cin >> a[i][j];
    }
  }
  int res = 0;
  for (int diag = 2; diag <= n + m; ++diag) {
    memset(f, 0, sizeof(f));
    int vcl = max(1, diag - m);
    for (int i = min(diag - 1, n); i >= vcl; --i) {
      int j = diag - i; 
      for (int t = 0; t < 3; ++t) {
        f[i][0] = max(f[i][0], f[i + 1][t]);
      }
      if (match_vertical(i, j)) {
        f[i][1] = max(f[i + 1][1], max(f[i + 2][0], f[i + 2][1])) + 1;
      }
      if (match_horizontal(i, j)) {
        for (int t = 0; t < 3; ++t) {
          f[i][2] = max(f[i][2], f[i + 1][t] + 1);
        }
      }
    }
    int mx = max({f[vcl][0], f[vcl][1], f[vcl][2]});
    res += mx;
  }
  cout << res;
}

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

  solve();

  return 0;
}

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