#include <iostream>
#include <vector>
#include <functional>
#include <cassert>
using namespace std;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
vector<pair<int, int>> ed;
int N = 0;
{
string g[n];
for (int i = 0; i < n; i++)
cin >> g[i];
vector<vector<int>> vis(n, vector<int>(m, -1));
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (g[i][j] != 'W') continue;
if (i - 1 >= 0 && g[i - 1][j] == 'G' && \
i - 2 >= 0 && g[i - 2][j] == 'R'){
vis[i][j] = vis[i - 1][j] = vis[i - 2][j] = N;
N++;
}
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (g[i][j] != 'W') continue;
if (j - 1 >= 0 && g[i][j - 1] == 'G' && \
j - 2 >= 0 && g[i][j - 2] == 'R'){
if (vis[i][j] != -1)
ed.emplace_back(vis[i][j], N);
if (vis[i][j - 1] != -1)
ed.emplace_back(vis[i][j - 1], N);
if (vis[i][j - 2] != -1)
ed.emplace_back(vis[i][j - 2], N);
N++;
}
}
}
}
vector<vector<int>> g(N);
for (auto &[u, v]: ed){
g[u].push_back(v);
g[v].push_back(u);
}
vector<vector<int>> dp(N, vector<int>(2));
vector<bool> vis(N);
function<void(int, int)> dfs = [&](int u, int pa){
vis[u] = 1;
dp[u][1] = 1;
for (auto &v: g[u]){
if (v == pa) continue;
if (vis[v]){
assert(false);
}
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
};
int ans = 0;
for (int i = 0; i < N; i++){
if (!vis[i]){
dfs(i, -1);
ans += max(dp[i][0], dp[i][1]);
}
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
320 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
324 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
320 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
28 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
324 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
316 KB |
Output is correct |
14 |
Correct |
1 ms |
256 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
320 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
324 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
1 ms |
320 KB |
Output is correct |
25 |
Correct |
1 ms |
324 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
28 |
Halted |
0 ms |
0 KB |
- |