제출 #1144303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144303		Robert_junior	Dango Maker (JOI18_dango_maker)	C++20	0 / 100	133 ms	235328 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ins insert
#define all(x) x.begin(), x.end()
#define F first
#define S second
const int N  = 10001000;
char a[3001][3001];
vector<int>g[N];
int used[N], mt[N], timer, n, m;
bool dfs(int v){
    if(used[v] == timer) return false;
    used[v] = timer;
    for(auto to : g[v]){
        if(!mt[to]){
            mt[to] = v;
            mt[v] = to;
            return true;
        }
    }
    for(auto to : g[v]){
        if(dfs(mt[to])){
            mt[to] = v;
            mt[v] = to;
            return true;
        }
    }
    return false;
}
int func(int i, int j){
    return (i - 1) * m + j;
}
void solve(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin>>a[i][j];
        }
    }
    int cnt = n * m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cnt++;
            if(i + 2 <= n){
                if(a[i][j] == 'R'&& a[i + 1][j] == 'G' && a[i + 2][j] == 'W'){
                    g[cnt].pb(func(i + 2, j));
                }
            }
            if(j + 2 <= m){
                if(a[i][j] == 'R'&& a[i][j + 1] == 'G'&& a[i][j + 2] == 'W'){
                    g[cnt].pb(func(i, j + 2));
                }
            }
            if(i - 2 >= 1){
                if(a[i - 2][j] == 'R'&& a[i - 1][j] == 'G' && a[i][j] == 'W'){
                    g[cnt].pb(func(i, j));
                }
            }
            if(j - 2 >= 1){
                if(a[i][j - 2] == 'R'&& a[i][j - 1] == 'G'&& a[i][j] == 'W'){
                    g[cnt].pb(func(i, j));
                }
            }
        }
    }
    int ans = 0;
    for(int i = n * m + 1; i <= cnt; i++){
        timer++;
        if(dfs(i)){
            ans++;
        }
    }
    cout<<ans;
}
signed main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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