Submission #1144392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144392		Robert_junior	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	103 ms	211820 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  = 9000100;
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;
            return true;
        }
    }
    for(auto to : g[v]){
        if(dfs(mt[to]) && mt[to] != v ){
            mt[to] = v;
            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]; 
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i + 2 <= n && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W'){
                g[func(i, j)].pb(func(i + 2, j)); 
            }
            if(j + 2 <= m && a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W'){
                g[func(i, j)].pb(func(i, j + 2));
            }
        }
    }
    int ans = 0;
    for(int i = 1; i <= n * m; i++){
        timer++;
        ans += dfs(i);
    }
    cout<<ans<<'\n';
}
signed main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();
    }
}

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