Submission #751594

#	Time	Username	Problem	Language	Result	Execution time	Memory
751594		tch1cherin	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	210 ms	19020 KiB

dango_maker

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

void solve() {
  int N, M;
  cin >> N >> M;
  vector<string> s(N);
  for (auto &v : s) {
    cin >> v;
  }
  int ans = 0;
  for (int t = 0; t < N + M; t++) {
    vector<int> dp(3, -1e7);
    dp[0] = 0;
    for (int i = min(N - 1, t); i >= 0; i--) {
      int j = t - i;
      if (j >= M) {
        break;
      }
      if (s[i][j] == 'G') {
        vector<int> new_dp(3, -1e7);
        new_dp[0] = max({dp[0], dp[1], dp[2]});
        if (j > 0 && j < M - 1 && s[i][j - 1] == 'R' && s[i][j + 1] == 'W') {
          new_dp[1] = max(dp[0], dp[1]) + 1;
        }
        if (i > 0 && i < N - 1 && s[i - 1][j] == 'R' && s[i + 1][j] == 'W') {
          new_dp[2] = max(dp[0], dp[2]) + 1;
        }
        dp = new_dp;
      } else {
        dp[0] = max({dp[0], dp[1], dp[2]});
        dp[1] = dp[2] = -1e7;
      }
    }
    ans += max({dp[0], dp[1], dp[2]}); 
  }
  cout << ans << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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