제출 #1310863

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310863		syanvu	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	333 ms	71852 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], ok[n + 1][m + 1] = {}, dp[n + 1][3] = {};
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char c;
            cin >> 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){
                ok[i][j] ^= 1;
            }
            if(i + 2 <= n && a[i][j] == 0 && a[i + 1][j] == 1 && a[i + 2][j] == 2){
                ok[i][j] ^= 2;
            }
        }
    }
    int ans = 0;
    for(int sum = 2; sum <= n + m; sum++){
        bool re = 0;
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(sum - i < 1 || sum - i > m) continue;
            if(!re){
                dp[i][0] = dp[i][1] = dp[i][2] = 0;
                if((ok[i][sum - i] & 1)) dp[i][1] = 1;
                if((ok[i][sum - i] & 2)) dp[i][2] = 1;
                res = max(dp[i][1], dp[i][2]);
                re = 1;
                continue;
            }
            dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
            dp[i][1] = dp[i][2] = 0;
            if((ok[i][sum - i] & 1)){
                dp[i][1] = 1;
                int mx = 0;
                if(i > 1) mx = max(mx, dp[i - 1][1]);
                if(i > 2) mx = max({mx, dp[i - 2][0], dp[i - 2][1]});
                dp[i][1] += mx;
            }
            if((ok[i][sum - i] & 2)){
                dp[i][2] = 1;
                if(i > 1) dp[i][2] += max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
            }
            res = max({res, dp[i][0], dp[i][1], dp[i][2]});
        }
        ans += res;
    }
    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: 20 / 20
• Subtask 3: 67 / 67