제출 #678539

#제출 시각아이디문제언어결과실행 시간메모리
678539uyluluDango Maker (JOI18_dango_maker)C++17
0 / 100
133 ms246924 KiB
#include <bits/stdc++.h> using namespace std; #define ld long double #define int __int16_t #define endl "\n" const int N = 3e3; vector<int> adj[N*N + 1]; char grid[N + 1][N + 1]; map<pair<pair<int,int>,pair<int,int>>,int> mp; int dp[N*N + 1][2]; int f(int s,int pa,bool type) { if(dp[s][type] != -1) return dp[s][type]; int res = type; for(auto u : adj[s]) { if(u == pa) continue; res = (res + f(u,s,!type)); } return dp[s][type] = res; } signed main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n,m; cin>>n>>m; memset(dp,-1,sizeof(dp)); for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { cin>>grid[i][j]; } } int curr = 1; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { int cnt = 0; if(j <= m - 2 && grid[i][j] == 'R' && grid[i][j + 1] == 'G' && grid[i][j + 2] == 'W') { mp[{{i,j},{i,j + 2}}] = curr; // intersect G pair<pair<int,int>,pair<int,int>> tmp = {{i - 1,j + 1},{i + 1,j + 1}}; if(mp[tmp]) { adj[curr].push_back(mp[tmp]); adj[mp[tmp]].push_back(curr); } // intersect W tmp = {{i - 2,j + 2},{i - 2,j}}; if(mp[tmp]) { adj[curr].push_back(mp[tmp]); adj[mp[tmp]].push_back(curr); } curr++; cnt++; } if(i <= m - 2 && grid[i][j] == 'R' && grid[i + 1][j] == 'G' && grid[i + 2][j] == 'W') { mp[{{i,j},{i + 2,j}}] = curr; // intersect G pair<pair<int,int>,pair<int,int>> tmp = {{i + 1,j - 1},{i + 1,j + 1}}; if(mp[tmp]) { adj[curr].push_back(mp[tmp]); adj[mp[tmp]].push_back(curr); } curr++; cnt++; } if(cnt == 2) { adj[curr - 2].push_back(curr - 1); adj[curr - 1].push_back(curr - 2); } } } int kq = 0; for(int i = 1;i < curr;i++) { if(dp[i][0] == -1) { kq += max(f(i,-1,0),f(i,-1,1)); } } cout<<kq<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...