Submission #1198207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198207		aykhn	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	159 ms	9288 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int MXN = 3e3 + 5;

char a[MXN][MXN];
int used[MXN][MXN];

void _()
{
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> a[i][j];
  auto cr = [&](int x, int y)
  {
    if (y + 2 >= m) return false;
    return a[x][y] == 'R' && a[x][y + 1] == 'G' && a[x][y + 2] == 'W';
  };
  auto cd = [&](int x, int y)
  {
    if (x + 2 >= n) return false;
    return a[x][y] == 'R' && a[x + 1][y] == 'G' && a[x + 2][y] == 'W';
  };
  int res = 0;
  for (int d = 0; d < n + m - 1; d++)
  {
    int dp[m][2], ans = 0;
    for (int i = 0; i < m; i++) dp[i][0] = dp[i][1] = 0;
    for (int j = m - 1; j >= 0; j--)
    {
      int i = d - j;
      if (i < 0 || i >= n) continue;
      if (j + 1 < m) 
      {
        dp[j][0] = dp[j + 1][0];
        dp[j][1] = max(dp[j + 1][0], dp[j + 1][1]);
      }
      dp[j][0] = max(dp[j][0], (j + 3 < m ? max(dp[j + 3][0], dp[j + 3][1]) : 0));
      dp[j][1] = max(dp[j][1], (j + 3 < m ? max(dp[j + 3][0], dp[j + 3][1]) : 0));
      dp[j][0] += cr(i, j);
      dp[j][1] += cd(i, j);
      ans = max(dp[j][0], dp[j][1]);
    }
    res += ans;
  }
  cout << res << '\n';
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) _();
}

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