Submission #1102096

#TimeUsernameProblemLanguageResultExecution timeMemory
1102096_8_8_Dango Maker (JOI18_dango_maker)C++17
33 / 100
350 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e3 + 12, MOD = 998244353, M = 3e6 + 12; char a[N][N]; int n, m, res = 0, res1 = 0, v[N][N], it = 1, h[N][N], dp[M][2]; vector<int> g[M]; void add(int x, int y) { g[x].push_back(y); g[y].push_back(x); } bool vis[N * N]; void dfs(int v, int pr = -1) { vis[v] = 1; dp[v][1] = 1; for(int to:g[v]) { if(to == pr || vis[to]) continue; dfs(to, v); dp[v][0] += max(dp[to][0], dp[to][1]); dp[v][1] += dp[to][0]; } } void test() { cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> a[i][j]; } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(a[i][j] == 'G' && a[i][j - 1] == 'R' && a[i][j + 1] == 'W') { h[i][j - 1] = it++; } if(a[i][j] == 'G' && a[i - 1][j] == 'R' && a[i + 1][j] == 'W') { v[i - 1][j] = it++; } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(a[i][j] == 'G' && a[i][j - 1] == 'R' && a[i][j + 1] == 'W') { if(v[i][j - 1]) { add(v[i][j - 1], h[i][j - 1]); } if(v[i - 1][j]) { add(v[i - 1][j], h[i][j - 1]); } if(v[i - 2][j + 1]) { add(v[i - 2][j + 1], h[i][j - 1]); } } if(a[i][j] == 'G' && a[i - 1][j] == 'R' && a[i + 1][j] == 'W') { if(h[i - 1][j]) { add(v[i - 1][j], h[i - 1][j]); } if(h[i][j - 1]) { add(v[i - 1][j], h[i][j - 1]); } if(h[i + 1][j - 2]) { add(v[i - 1][j], h[i + 1][j - 2]); } } } } for(int i = 1; i < it; i++) { sort(g[i].begin(), g[i].end()); g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin()); } for(int i = 1; i < it; i++) { if(!vis[i]) { dfs(i); res += max(dp[i][0], dp[i][1]); } } cout << res << '\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; // cin >> t; while(t--) test(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...