제출 #682096

#제출 시각아이디문제언어결과실행 시간메모리
682096etheningDango Maker (JOI18_dango_maker)C++17
33 / 100
2084 ms10700 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; // RGW // template<class T> // struct dinic { // static constexpr T INF = numeric_limits<T>::max(); // struct edge { // int v, r; T c; // edge(int _v, int _r, T _c) : v{_v}, r{_r}, c{_c} {} // }; // int n, s, t; // vector<vector<edge>> G; // vector<int> d, arc; // dinic(int _n, int _s, int _t) : n{_n}, s{_s}, t{_t}, G(_n) {} // void add_edge(int u, int v, T c) { // G[u].emplace_back(v, (int)G[v].size(), c); // G[v].emplace_back(u, (int)G[u].size() - 1, 0); // } // int bfs() { // d.assign(n, 0), arc.assign(n, 0); // queue<int> q; // d[s] = 1, q.emplace(s); // while (!q.empty()) { // int u = q.front(); // q.pop(); // for (auto [v, r, c] : G[u]) { // if (!d[v] && c) { // d[v] = d[u] + 1; // if (v == t) return 1; // q.emplace(v); // } // } // } // return d[t]; // } // T dfs(int u, T f) { // if (u == t) return f; // T sum = 0; // for (int& i = arc[u]; i < (int)G[u].size(); ++i) { // auto& [v, r, c] = G[u][i]; // if (d[v] == d[u] + 1 && c) { // T res = dfs(v, min(f, c)); // if (res) { // c -= res, G[v][r].c += res; // sum += res, f -= res; // if (!f) return sum; // } else { // d[v] = 0; // } // } // } // return sum; // } // T max_flow() { // T sum = 0; // while (bfs()) { // while (T res = dfs(s, INF)) { // sum += res; // } // } // return sum; // } // }; // bool dfs(int cur) { // for (int nxt : va[cur]) { // if (!visitb[nxt]) { // visitb[nxt] = true; // clrS.push(nxt); // if (mb[nxt] == 0 || dfs(mb[nxt])) { // ma[cur] = nxt; // mb[nxt] = cur; // return true; // } // } // } // return false; // } // int bipartite_matching() { // memset(ma, -1, sizeof(ma)); // memset(mb, -1, sizeof(mb)); // int ret = 0; // for (int i = 1; i <= cnt; i++) { // while (!clrS.empty()) { // visitb[clrS.top()] = false; // clrS.pop(); // } // if (dfs(i)) ++ret; // } // return ret; // } int main() { int n, m; cin.tie(0)->sync_with_stdio(0); cin >> n >> m; vector<string> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } int ans = 0; for (int k = 0; k < n + m - 1; k++) { vector dp(n, vector(2, vector(2, 0))); for (int i = max(0, k - m + 1); i < min(n, k + 1); i++) { int j = k - i; if (i == 0) { dp[i][0][0] = 0; } else { dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][0]); dp[i][0][0] = max(dp[i][0][0], dp[i - 1][0][1]); dp[i][0][0] = max(dp[i][0][0], dp[i - 1][1][0]); } if (s[i][j] != 'G') continue; if (j - 1 >= 0 && j + 1 < m && s[i][j - 1] == 'R' && s[i][j + 1] == 'W') { if (i == 0) { dp[i][1][0] = 1; } else { dp[i][1][0] = max(dp[i][1][0], dp[i - 1][0][0] + 1); dp[i][1][0] = max(dp[i][1][0], dp[i - 1][1][0] + 1); } } if (i - 1 >= 0 && i + 1 < n && s[i - 1][j] == 'R' && s[i + 1][j] == 'W') { if (i == 0) { dp[i][0][1] = 1; } else { dp[i][0][1] = max(dp[i][0][1], dp[i - 1][0][0] + 1); dp[i][0][1] = max(dp[i][0][1], dp[i - 1][0][1] + 1); } } } int cur = 0; cur = max(cur, dp[min(n, k + 1) - 1][0][0]); cur = max(cur, dp[min(n, k + 1) - 1][0][1]); cur = max(cur, dp[min(n, k + 1) - 1][1][0]); ans += cur; } cout << ans << endl; // int cnt, cnt2; // cnt = cnt2 = 0; // vector a(n, vector<int>(n)); // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // if (s[i][j] != 'R') continue; // if (j + 2 < m) { // if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') { // ++cnt; // // a[i][j] = cnt; // // a[i][j + 1] = cnt; // // a[i][j + 2] = cnt; // } // } // if (i + 2 < n) { // if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') { // ++cnt2; // // b[i][j]= cnt2; // // b[i + 1][j]= cnt2; // // b[i + 2][j]= cnt2; // } // } // } // } // return 0; // dinic<int> D(cnt + cnt2 + 2, 0, 1); // for (int i = 1; i <= cnt; i++) { // D.add_edge(0, i + 1, 1); // } // for (int i = 1; i <= cnt2; i++) { // D.add_edge(cnt + i + 1, 1, 1); // } // int cnt3 = 0; // int cnt4 = 0; // for (int k = 0; k < n + m - 1; k++) { // int prevcnt = -200; // int prevdex = -200; // int prevcnt2 = -200; // int prevdex2 = -200; // for (int i = max(0, k - m + 1); i < min(n, k + 1); i++) { // int j = k - i; // if (s[i][j] != 'R') continue; // if (j + 2 < m) { // if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') { // ++cnt3; // if (prevdex == i - 1 || prevdex == i - 2) { // D.add_edge(cnt3 + 1, cnt + prevcnt + 1, D.INF); // // cout << prevdex << " -> " << i << endl; // } // if (prevdex2 == i - 2) { // D.add_edge(cnt3 + 1, cnt + prevcnt2 + 1, D.INF); // // cout << prevdex2 << " -> " << i << endl; // } // if (i + 2 < n && s[i + 1][j] == 'G' && s[i + 2][j] == 'W') { // D.add_edge(cnt3 + 1, cnt + cnt4 + 1 + 1, D.INF); // // cout << i << " -> " << i << endl; // } // // b[i][j]= cnt2; // // b[i + 1][j]= cnt2; // // b[i + 2][j]= cnt2; // } // } // if (i + 2 < n) { // if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') { // ++cnt4; // swap(prevcnt, prevcnt2); // swap(prevdex, prevdex2); // prevcnt = cnt3; // prevdex = i; // // a[i][j] = cnt; // // a[i][j + 1] = cnt; // // a[i][j + 2] = cnt; // } // } // } // } // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // if (a[i][j] != 0 && b[i][j] != 0) { // D.add_edge(a[i][j] + 1, cnt + b[i][j] + 1, D.INF); // // va[a[i][j]].push_back(b[i][j]); // } // } // } // cout << cnt + cnt2 - D.max_flow() << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...