Submission #770317

#	Time	Username	Problem	Language	Result	Execution time	Memory
770317		gun_gan	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	18 ms	468 KiB

dango_maker

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

const int MX = 3005;

int N, M;
int dp[MX][3];
string c[MX];

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

      cin >> N >> M;
      for(int i = 0; i < N; i++) cin >> c[i];
      
      int ans = 0;
      for(int s = 0; s < N + M - 1; s++) {
            for(int i = 0; i < MX; i++) 
                  for(int k = 0; k < 3; k++) dp[i][k] = 0;

            for(int i = 0; i <= min(s, N - 1); i++) { // i + j = s
                  int j = s - i;

                  dp[i][0] = (i - 1 < 0 ? 0 : max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}));
                  if(c[i][j] == 'G') {
                        if(j - 1 >= 0 && j + 1 < M && c[i][j - 1] == 'R' && c[i][j + 1] == 'W') {
                              dp[i][1] = (i - 1 < 0 ? 0 : max(dp[i - 1][0], dp[i - 1][1])) + 1;
                        } 
                        if(i - 1 >= 0 && i + 1 < N && c[i - 1][j] == 'R' && c[i + 1][j] == 'W') {
                              dp[i][2] = (i - 1 < 0 ? 0 : max(dp[i - 1][0], dp[i - 1][2])) + 1;
                        }
                  }
            }

            ans += max({dp[min(s, N - 1)][0], dp[min(s, N - 1)][1], dp[min(s, N - 1)][2]});
      }

      cout << ans << '\n';
}

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