Submission #99610

#	Time	Username	Problem	Language	Result	Execution time	Memory
99610		lovemathboy	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	375 ms	81880 KiB

dango_maker

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

int n, m;
char a[3005][3005];
int memo[3005][3005][2];

inline bool hori(int x, int y) {
	if (y + 2 >= m) return false;
	if (a[x][y] == 'R' && a[x][y+1] == 'G' && a[x][y+2] == 'W') return true;
	return false;
}

inline bool vert(int x, int y) {
	if (x + 2 >= n) return false;
	if (a[x][y] == 'R' && a[x+1][y] == 'G' && a[x+2][y] == 'W') return true;
	return false;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", a[i]);
		for (int j = 0; j < m; j++) memo[i][j][0] = 0, memo[i][j][1] = 0;
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			if (j > 0) {
				memo[i-j][j][0] = max(memo[i-j+1][j-1][0], memo[i-j+1][j-1][1]);
				memo[i-j][j][1] = memo[i-j+1][j-1][1];
			}
			if (j > 2) {
				memo[i-j][j][1] = max(memo[i-j][j][1], memo[i-j+3][j-3][0]);
			}
			if (a[i-j][j] != 'R') continue;
			if (hori(i-j, j)) memo[i-j][j][0]++;
			if (vert(i-j, j)) memo[i-j][j][1]++;
		}
	}
	for (int i = 1; i < m; i++) {
		for (int j = 0; j < m-i; j++) {
			if (i+j >= m || n-j-1 < 0) break;
			if (j > 0) {
				memo[n-j-1][i+j][0] = max(memo[n-j][i+j-1][0], memo[n-j][i+j-1][1]);
				memo[n-j-1][i+j][1] = memo[n-j][i+j-1][1];
			}
			if (j > 2) {
				memo[n-j-1][i+j][1] = max(memo[n-j][i+j-1][1], memo[n-j+2][i+j-3][0]);
			}
			if (a[n-j-1][i+j] != 'R') continue;
			if (hori(n-j-1, i+j)) memo[n-j-1][i+j][0]++;
			if (vert(n-j-1, i+j)) memo[n-j-1][i+j][1]++;
		}
	}
	for (int i = 0; i < m; i++) {
		ans += max(memo[0][i][0], memo[0][i][1]);
	}
	for (int i = 1; i < n; i++) {
		ans += max(memo[i][m-1][0], memo[i][m-1][1]);
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
   ~~~~~^~~~~~~~~~~~

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