제출 #780140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780140		mychecksedad	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	93 ms	262144 KiB

dango_maker

/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1e7+100, M = 1e5+10, K = 20;


int n, m;
string s[N];
vector<bool> g[N][2];
vector<bool> v(N);
vector<array<bool, 2>> vis(N);
int arr[2][3] = {
  {
    0, 
    m-1, 
    2*m-2 
  },
  { 
    0,
    -m+1,
    -2*m+2
  }
};

pair<int, int> dfs(int x, int p){
  if(!v[x]) return {0, 0};
  pair<int, int> ans = {1, 0};
  vis[x][p] = 1;
  for(auto y: g[x][p]){
    pair<int, int> u = {arr[p][y], 1-p};
    if(vis[u.first][u.second]) continue;
    auto dp = dfs(u.first, u.second);
    ans.first += dp.second;
    ans.second += max(dp.first, dp.second);
  }
  return ans;
}

void solve(){
  cin >> n >> m;
  for(int i = 0; i < n; ++i) cin >> s[i];
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      g[i*m+j][0].resize(3);
      g[i*m+j][1].resize(3);
      if(i < n - 2){
        int x = i*m+j;
        if(s[i][j] == 'R' && s[i+1][j] == 'G' && s[i+2][j] == 'W'){
          if(v[x]) g[x][0].pb(0), g[x][1].pb(0);
          if(v[x+m]) g[x][0].pb(1), g[x+m-1][1].pb(1);
          if(v[x+m+m]) g[x][0].pb(2), g[x+2*m-2][1].pb(2);
          v[x] = v[x+m] = v[x+m+m] = 1;
        }
      }
      if(j < m-2){
        int x = i*m+j;

        if(s[i][j] == 'R' && s[i][j+1] == 'G' && s[i][j+2] == 'W'){
          if(v[x]) g[x][1].pb(0), g[x][0].pb(0);
          if(v[x+1]) g[x][1].pb(1), g[x+1-m][0].pb(1);
          if(v[x+2]) g[x][1].pb(2), g[x+2-2*m][0].pb(2);
          v[x] = v[x+1] = v[x+2] = 1;
        }
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(s[i][j] != 'R') continue;
      if(!vis[i*m+j][0] || !vis[i*m+j][1]){
        int t = 0;
        if(!vis[i*m+j][1])
          t = 1;
        auto dp = dfs(i*m+j, t);
        ans += max(dp.first, dp.second);
      }
    }
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  // cin >> T;aa=T;
  while(T--){
    // cout << "Case #" << aa-T << ": ";
    solve();
    cout << '\n';
  }
  return 0;
 
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:91:14: warning: unused variable 'aa' [-Wunused-variable]
   91 |   int T = 1, aa;
      |              ^~

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