oj.uz

Submission #411703

# Submission time Handle Problem Language Result Execution time Memory
411703 2021-05-25T18:31:36 Z nichke Dango Maker (JOI18_dango_maker) C++14
0 / 100
 136 ms 262148 KB 
#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][6005];
bool valid[6005][6005][2];

int calc(int row, int prev) {
	if (row == diag) 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

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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 136 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -