Submission #411706

#	Time	Username	Problem	Language	Result	Execution time	Memory
411706		nichke	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	669 ms	56780 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int ans;
int n, m, diag;
char ar[6005][6005];
int dp[6005][3];
bool valid[6005][6005][2];

int calc(int row, int prev) {
	if (row > n) return 0;
	if (dp[row][prev] != -1) return dp[row][prev];
	int ans = calc(row + 1, 0);
	if (!prev) {
		if (valid[row][diag - row][1]) ans = max(ans, 1 + calc(row + 1, 1));
		if (valid[row][diag - row][2]) ans = max(ans, 1 + calc(row + 1, 2));
	}
	if (prev == 1) {
		if (valid[row][diag - row][1]) ans = max(ans, 1 + calc(row + 1, 1));
	}
	if (prev == 2) {
		if (valid[row][diag - row][2]) ans = max(ans, 1 + calc(row + 1, 2));
	}
	return dp[row][prev] = ans;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> ar[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			valid[i][j][1] = (i < n && i > 1 && ar[i][j] == 'G' && ar[i - 1][j] == 'R' && ar[i + 1][j] == 'W');
			valid[i][j][2] = (j < m && j > 1 && ar[i][j] == 'G' && ar[i][j - 1] == 'R' && ar[i][j + 1] == 'W');
		}
	}
	for (int i = 2; i <= n + m; i++) {
		memset(dp, -1, sizeof dp); diag = i;
		ans += calc(1, 0);
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'long long int _Z4calcxx.part.0(long long int, long long int)':
dango_maker.cpp:18:31: warning: array subscript 2 is above array bounds of 'bool [2]' [-Warray-bounds]
   18 |   if (valid[row][diag - row][2]) ans = max(ans, 1 + calc(row + 1, 2));
      |       ~~~~~~~~~~~~~~~~~~~~~~~~^
dango_maker.cpp:24:31: warning: array subscript 2 is above array bounds of 'bool [2]' [-Warray-bounds]
   24 |   if (valid[row][diag - row][2]) ans = max(ans, 1 + calc(row + 1, 2));
      |       ~~~~~~~~~~~~~~~~~~~~~~~~^
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:41:17: warning: array subscript 2 is above array bounds of 'bool [2]' [-Warray-bounds]
   41 |    valid[i][j][2] = (j < m && j > 1 && ar[i][j] == 'G' && ar[i][j - 1] == 'R' && ar[i][j + 1] == 'W');
      |    ~~~~~~~~~~~~~^

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