oj.uz

Submission #99609

# Submission time Handle Problem Language Result Execution time Memory
99609 2019-03-05T15:50:02 Z lovemathboy Dango Maker (JOI18_dango_maker) C++14
13 / 100
 5 ms 640 KB 
#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 (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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 428 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 428 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 3 ms 428 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -