#include <bits/stdc++.h>
using namespace std;
const int N = 3010;
const string d = "RGW";
int n, m, ans;
int f[N][N], cnt[N][N];
string c[N];
vector<pair<pair<int, int>, bool>> p;
namespace Subtask1 {
bool check() {
return n <= 5 && m <= 5;
}
int len = 0;
void dfs(int x, int num) {
if (ans >= num + len - x + 1) return;
if (x == len) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (cnt[i][j] > 1) return;
ans = max(ans, num);
return;
}
dfs(x + 1, num);
if (p[x].second) {
for (int i = p[x].first.first; i <= p[x].first.first + 2; i++)
cnt[i][p[x].first.second]++;
} else {
for (int i = p[x].first.second; i <= p[x].first.second + 2; i++)
cnt[p[x].first.first][i]++;
}
dfs(x + 1, num + 1);
if (p[x].second) {
for (int i = p[x].first.first; i <= p[x].first.first + 2; i++)
cnt[i][p[x].first.second]--;
} else {
for (int i = p[x].first.second; i <= p[x].first.second + 2; i++)
cnt[p[x].first.first][i]--;
}
}
void solve() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m - 2; j++) {
bool vis = true;
for (int k = j; k <= j + 2; k++)
if (c[i][k] != d[k - j]) {
vis = false;
break;
}
if (vis) p.push_back(make_pair(make_pair(i, j), 0));
}
for (int j = 1; j <= m; j++)
for (int i = 1; i <= n - 2; i++) {
bool vis = true;
for (int k = i; k <= i + 2; k++)
if (c[k][j] != d[k - i]) {
vis = false;
break;
}
if (vis) p.push_back(make_pair(make_pair(i, j), 1));
}
len = p.size();
dfs(0, 0);
printf("%d\n", ans);
}
}
namespace Subtask2_3 {
void solve() {
for (int i = 2; i <= n + m; i++) {
int sum = 0;
memset(f, 0, sizeof(f));
for (int j = max(1, i - m), k = i - j; j <= n && k; j++, k--) {
f[j][0] = max(max(f[j - 1][0], f[j - 1][1]), f[j - 1][2]);
if (c[j][k] == 'G') {
if (c[j - 1][k] == 'R' && c[j + 1][k] == 'W') f[j][1] = max(f[j][1], max(f[j - 1][0], f[j - 1][1]) + 1);
if (c[j][k - 1] == 'R' && c[j][k + 1] == 'W') f[j][2] = max(f[j][2], max(f[j - 1][0], f[j - 1][2]) + 1);
}
sum = max(max(sum, f[j][0]), max(f[j][1], f[j][2]));
}
ans += sum;
}
printf("%d\n", ans);
}
}
int main() {
// freopen("dumpling.in", "r", stdin);
// freopen("dumpling.out", "w", stdout);
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
cin >> c[i];
c[i] = " " + c[i];
}
if (Subtask1::check()) Subtask1::solve();
else Subtask2_3::solve();
return 0;
}
Compilation message
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
33 ms |
36596 KB |
Output is correct |
19 |
Correct |
47 ms |
36444 KB |
Output is correct |
20 |
Correct |
49 ms |
36444 KB |
Output is correct |
21 |
Correct |
55 ms |
36444 KB |
Output is correct |
22 |
Correct |
55 ms |
36444 KB |
Output is correct |
23 |
Correct |
53 ms |
36444 KB |
Output is correct |
24 |
Correct |
54 ms |
36464 KB |
Output is correct |
25 |
Correct |
29 ms |
36492 KB |
Output is correct |
26 |
Correct |
30 ms |
36440 KB |
Output is correct |
27 |
Correct |
53 ms |
36440 KB |
Output is correct |
28 |
Correct |
53 ms |
36440 KB |
Output is correct |
29 |
Correct |
53 ms |
36440 KB |
Output is correct |
30 |
Correct |
53 ms |
36440 KB |
Output is correct |
31 |
Correct |
54 ms |
36440 KB |
Output is correct |
32 |
Correct |
54 ms |
36440 KB |
Output is correct |
33 |
Correct |
55 ms |
36692 KB |
Output is correct |
34 |
Correct |
54 ms |
36464 KB |
Output is correct |
35 |
Correct |
55 ms |
36440 KB |
Output is correct |
36 |
Correct |
53 ms |
36464 KB |
Output is correct |
37 |
Correct |
54 ms |
36444 KB |
Output is correct |
38 |
Correct |
56 ms |
36468 KB |
Output is correct |
39 |
Correct |
54 ms |
36440 KB |
Output is correct |
40 |
Correct |
54 ms |
36440 KB |
Output is correct |
41 |
Correct |
53 ms |
36444 KB |
Output is correct |
42 |
Correct |
53 ms |
36444 KB |
Output is correct |
43 |
Correct |
55 ms |
36700 KB |
Output is correct |
44 |
Correct |
58 ms |
36444 KB |
Output is correct |
45 |
Correct |
56 ms |
36468 KB |
Output is correct |
46 |
Correct |
53 ms |
36444 KB |
Output is correct |
47 |
Correct |
53 ms |
36464 KB |
Output is correct |
48 |
Correct |
54 ms |
36460 KB |
Output is correct |
49 |
Correct |
54 ms |
36464 KB |
Output is correct |
50 |
Correct |
55 ms |
36452 KB |
Output is correct |
51 |
Correct |
53 ms |
36444 KB |
Output is correct |
52 |
Correct |
56 ms |
36368 KB |
Output is correct |
53 |
Correct |
53 ms |
36444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
33 ms |
36596 KB |
Output is correct |
19 |
Correct |
47 ms |
36444 KB |
Output is correct |
20 |
Correct |
49 ms |
36444 KB |
Output is correct |
21 |
Correct |
55 ms |
36444 KB |
Output is correct |
22 |
Correct |
55 ms |
36444 KB |
Output is correct |
23 |
Correct |
53 ms |
36444 KB |
Output is correct |
24 |
Correct |
54 ms |
36464 KB |
Output is correct |
25 |
Correct |
29 ms |
36492 KB |
Output is correct |
26 |
Correct |
30 ms |
36440 KB |
Output is correct |
27 |
Correct |
53 ms |
36440 KB |
Output is correct |
28 |
Correct |
53 ms |
36440 KB |
Output is correct |
29 |
Correct |
53 ms |
36440 KB |
Output is correct |
30 |
Correct |
53 ms |
36440 KB |
Output is correct |
31 |
Correct |
54 ms |
36440 KB |
Output is correct |
32 |
Correct |
54 ms |
36440 KB |
Output is correct |
33 |
Correct |
55 ms |
36692 KB |
Output is correct |
34 |
Correct |
54 ms |
36464 KB |
Output is correct |
35 |
Correct |
55 ms |
36440 KB |
Output is correct |
36 |
Correct |
53 ms |
36464 KB |
Output is correct |
37 |
Correct |
54 ms |
36444 KB |
Output is correct |
38 |
Correct |
56 ms |
36468 KB |
Output is correct |
39 |
Correct |
54 ms |
36440 KB |
Output is correct |
40 |
Correct |
54 ms |
36440 KB |
Output is correct |
41 |
Correct |
53 ms |
36444 KB |
Output is correct |
42 |
Correct |
53 ms |
36444 KB |
Output is correct |
43 |
Correct |
55 ms |
36700 KB |
Output is correct |
44 |
Correct |
58 ms |
36444 KB |
Output is correct |
45 |
Correct |
56 ms |
36468 KB |
Output is correct |
46 |
Correct |
53 ms |
36444 KB |
Output is correct |
47 |
Correct |
53 ms |
36464 KB |
Output is correct |
48 |
Correct |
54 ms |
36460 KB |
Output is correct |
49 |
Correct |
54 ms |
36464 KB |
Output is correct |
50 |
Correct |
55 ms |
36452 KB |
Output is correct |
51 |
Correct |
53 ms |
36444 KB |
Output is correct |
52 |
Correct |
56 ms |
36368 KB |
Output is correct |
53 |
Correct |
53 ms |
36444 KB |
Output is correct |
54 |
Execution timed out |
2032 ms |
36440 KB |
Time limit exceeded |
55 |
Halted |
0 ms |
0 KB |
- |