Submission #682098

#	Time	Username	Problem	Language	Result	Execution time	Memory
682098		ethening	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	256 ms	183072 KiB

dango_maker

#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 dp[6005][3005][2][2];
string s[3005];

int main() {
	int n, m;
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	int ans = 0;

	for (int k = 0; k < n + m - 1; k++) {
		for (int i = max(0, k - m + 1); i < min(n, k + 1); i++) {
			int j = k - i;
			if (i == 0) {
				dp[k][i][0][0] = 0;
			}
			else {
				dp[k][i][0][0] = max(dp[k][i][0][0], dp[k][i - 1][0][0]);
				dp[k][i][0][0] = max(dp[k][i][0][0], dp[k][i - 1][0][1]);
				dp[k][i][0][0] = max(dp[k][i][0][0], dp[k][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[k][i][1][0] = 1;
				}
				else {
					dp[k][i][1][0] = max(dp[k][i][1][0], dp[k][i - 1][0][0] + 1);
					dp[k][i][1][0] = max(dp[k][i][1][0], dp[k][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[k][i][0][1] = 1;
				}
				else {
					dp[k][i][0][1] = max(dp[k][i][0][1], dp[k][i - 1][0][0] + 1);
					dp[k][i][0][1] = max(dp[k][i][0][1], dp[k][i - 1][0][1] + 1);
				}
			}
		}
		int cur = 0;
		cur = max(cur, dp[k][min(n, k + 1) - 1][0][0]);
		cur = max(cur, dp[k][min(n, k + 1) - 1][0][1]);
		cur = max(cur, dp[k][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;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67