Submission #79962

#	Time	Username	Problem	Language	Result	Execution time	Memory
79962		Just_Solve_The_Problem	Dango Maker (JOI18_dango_maker)	C++11	100 / 100	304 ms	47828 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

const int N = (int)3e3 + 7;

int n, m;
char C[N][N];
int c[N][N];
int dp[3][N];

main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    getchar();
    for (int j = 1; j <= m; j++) {
      C[i][j] = getchar();
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (C[i][j] == 'G') {
	if (C[i][j - 1] == 'R' && C[i][j + 1] == 'W')
	  c[i][j] |= 1;
        if (C[i - 1][j] == 'R' && C[i + 1][j] == 'W')
	  c[i][j] |= 2;
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int x = i;
    int y = 1;
    memset(dp, 0, sizeof dp);
    while (x >= 1 && y <= m) {
      dp[0][y] = dp[0][y - 1];
      dp[1][y] = dp[1][y - 1];
      dp[2][y] = dp[2][y - 1];
      dp[0][y] = max(dp[1][y - 1], dp[2][y - 1]);
      if (c[x][y] & 1) {
	dp[1][y] = max(dp[1][y - 1], dp[0][y - 1]) + 1;
      }
      if (c[x][y] & 2) {
	dp[2][y] = max(dp[2][y - 1], dp[0][y - 1]) + 1;
      }
      x--;
      y++;
    }
    ans += max(dp[0][y - 1], max(dp[1][y - 1], dp[2][y - 1]));
    //cout << i << ' ' << ans << endl;
  }
  
  for (int i = 2; i <= m; i++) {
    int x = n;
    int y = i;
    memset(dp, 0, sizeof dp);
    while (x >= 1 && y <= m) {
      dp[0][y] = dp[0][y - 1];
      dp[1][y] = dp[1][y - 1];
      dp[2][y] = dp[2][y - 1];
      dp[0][y] = max(dp[1][y - 1], dp[2][y - 1]);
      if (c[x][y] & 1) {
	dp[1][y] = max(dp[1][y - 1], dp[0][y - 1]) + 1;
      }
      if (c[x][y] & 2) {
	dp[2][y] = max(dp[2][y - 1], dp[0][y - 1]) + 1;
      }
      x--;
      y++;
    }
    ans += max(dp[0][y - 1], max(dp[1][y - 1], dp[2][y - 1]));
    //cout << i << ' ' << ans << endl;
  }
  cout << ans;
}

Compilation message (stderr)

dango_maker.cpp:12:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~

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