제출 #1310818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310818		syanvu	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	41 ms	916 KiB

dango_maker

// #pragma optimize ("g",on)
// #pragma GCC optimize ("inline")
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC optimize ("03")
#include <bits/stdc++.h>

#define pb push_back
#define SS ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
// #define int long long
#define all(v) v.begin(),v.end()
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int N = 3077, inf = 1e9, mod = 998244353;

vector<int> g[N][N];
pair<int, int> was[N][N];
int used[N][N], timer;

bool dfs(int x, int y){
    if(used[x][y] == timer) return false;
    used[x][y] = timer;
    for(int t : g[x][y]){
        if(t == 1){
            bool ch = 0;
            for(int i = y; i <= y + 2; i++){
                if(was[x][i].first > 0 && !dfs(was[x][i].first, was[x][i].second)){
                    ch = 1;
                    break;
                }
            }
            if(!ch){
                for(int i = y; i <= y + 2; i++){
                    was[x][i] = {x, y};
                }
                return true;
            }
        }
        if(t == 2){
            bool ch = 0;
            for(int i = x; i <= x + 2; i++){
                if(was[i][y].first > 0 && !dfs(was[i][y].first, was[i][y].second)){
                    ch = 1;
                    break;
                }
            }
            if(!ch){
                for(int i = x; i <= x + 2; i++){
                    was[i][y] = {x, y};
                }
                return true;
            }
        }
    }
    return false;
}

void solve(){
    int n, m;
    cin >> n >> m;
    int a[n + 1][m + 1];
    char s[n + 1][m + 1];
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char c;
            cin >> c;
            s[i][j] = c;
            if(c == 'R') a[i][j] = 0;
            if(c == 'G') a[i][j] = 1;
            if(c == 'W') a[i][j] = 2;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(j + 2 <= m && a[i][j] == 0 && a[i][j + 1] == 1 && a[i][j + 2] == 2){
                g[i][j].push_back(1);
            }
            if(i + 2 <= n && a[i][j] == 0 && a[i + 1][j] == 1 && a[i + 2][j] == 2){
                g[i][j].push_back(2);
            }
        }
    }
    int ans = 0;
    // cout << g[1][1].size();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] != 0 || was[i][j].first > 0) continue;
            timer++;
            if(dfs(i, j)) ans++;
        }
    }
    cout << ans;
}

signed main(){
    SS
    // freopen("trains.in", "r", stdin);
    // freopen("trains.out", "w", stdout);

    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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