Submission #1290944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290944		mhaer	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	230 ms	327680 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")

int r;
int c;

void once(vector<string>& input, vector<vector<vector<int>>>& dp, int rr, int cc) {
  int umd = 0;
  if (rr-1 >= 0 && rr+1 < r) {
    if (input[rr-1][cc] == 'W' && input[rr][cc] == 'G' && input[rr+1][cc] == 'R') {
      umd++;
    }
  }
  
  int lmr = 0;  
  if (cc-1 >= 0 && cc+1 < c) {
    if (input[rr][cc-1] == 'R' && input[rr][cc] == 'G' && input[rr][cc+1] == 'W') {
      lmr++;
    }
  }

  if (rr > 0 && cc > 0) {
    dp[rr][cc][0] = max(dp[rr-1][cc-1][0], max(dp[rr-1][cc-1][1], dp[rr-1][cc-1][2]));    
    dp[rr][cc][1] = max(dp[rr-1][cc-1][0], dp[rr-1][cc-1][1]) + umd;
    dp[rr][cc][2] = max(dp[rr-1][cc-1][0], dp[rr-1][cc-1][2]) + lmr;
  } else {
    dp[rr][cc][0] = 0;
    dp[rr][cc][1] = umd;
    dp[rr][cc][2] = lmr;
  }
}

int solve(vector<string>& grid, int rr) {
  return 1;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
    cin >> r >> c;
    vector<string> input(r);
    vector<vector<vector<int>>> dp(r, vector<vector<int>>(c, vector<int>(3, 0)));
    for (auto& i : input) cin >> i;

    for (int i = 0;i < c;i++) {
      for (int rr = 0;rr < r/2;rr++) {
        swap(input[rr][i], input[r-rr-1][i]);
      }
    }
    
    for (int rr = 0;rr < r;rr++) {
      for (int cc = 0;cc < c;cc++) {
        once(input, dp, rr, cc);
      }
    }

    int sum = 0;
    for (int cc = 0;cc < c;cc++) {
      sum += max(dp[r-1][cc][0], max(dp[r-1][cc][1], dp[r-1][cc][2]));
    }

    for (int rr = 0;rr < r-1;rr++) {
      sum += max(dp[rr][c-1][0], max(dp[rr][c-1][1], dp[rr][c-1][2]));
    }

    cout << sum << "\n";

    
}

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