제출 #1006786

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

dango_maker

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define ll long long
#define pll pair<ll, ll>
#define pb push_back

vector<int> dq[3010][3010];
int a[3021][3021];
int kto[9000001];
int cnt[3];
int pos[9000001];
vector<int> q[9000001];

void dfs(int v){
    pos[v] = 1;
    cnt[kto[v]] ++;
    for(int to: q[v]){
        if(pos[to]) continue;
        dfs(to);
    }
}



void solve(){   
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            a[i][j] = c;
        }
    }
    int ls = 0;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(j >= 3 and a[i][j] == 'W' and a[i][j-1] == 'G' and a[i][j - 2] == 'R'){
                dq[i][j].pb(++ls);
                dq[i][j-1].pb(ls);
                dq[i][j-2].pb(ls);
                kto[ls] = 1;
            }
            if(i >= 3 and a[i][j] == 'W' and a[i-1][j] == 'G' and a[i-2][j] == 'R'){
                dq[i][j].pb(++ls);
                dq[i-1][j].pb(ls);
                dq[i-2][j].pb(ls);
                kto[ls] = 2;
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            for(int x: dq[i][j]){
                for(int y: dq[i][j]){
                    if(x != y) q[x].pb(y);
                }
            }
        }
    }
    ll ans = 0;
    for(int i=1; i<=ls; i++){
        if(pos[i]) continue;
        cnt[1] = cnt[2] = 0;
        dfs(i);
        ans += max(cnt[1], cnt[2]);
    }
    cout<<ans<<'\n';
}

int main(){
    solve();
}

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