Submission #1105981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105981		SoulKnight	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	14 ms	71760 KiB

dango_maker

// #include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define ln '\n'

const int N = 3e3 + 5;
const string S = "RGW";

struct hhh{
    int horiz = -1, vert = -1;
} a[N][N];


int n, m, glit = 1;
string grid[N];
vector<int> adj[N*N/3];
bool vis[N*N/3];
int dp[N*N/3][2];

void dfs(int u, int p){
    int take = 0, no_take = 0;
    vis[u] = 1;
    for (auto v: adj[u]){
        if (v == p) continue;
        dfs(v, u);
        take += dp[v][1];
        no_take += dp[v][0];
    }
    dp[u][0] = take;
    dp[u][1] = 1 + no_take;
}

void solve(){
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> grid[i];
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            bool ok = true;
            for (int k = 0; k <= 2; k++){
                int ti = i, tj = j + k;
                if (ti < 0 || ti > n-1 || tj < 0 || tj > m-1) {ok = false; break;}
                if (grid[ti][tj] != S[k]) {ok = false; break;}
            }
            if (ok) a[i][j+1].horiz = glit++;

            ok = true;
            for (int k = 0; k <= 2; k++){
                int ti = i+k, tj = j;
                if (ti < 0 || ti > n-1 || tj < 0 || tj > m-1) {ok = false; break;}
                if (grid[ti][tj] != S[k]) {ok = false; break;}
            }
            if (ok) a[i+1][j].vert = glit++;
        }
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++){
            int u = a[i][j].horiz, v = a[i][j].vert;
            if (u != -1 && v != -1) adj[u].push_back(v), adj[v].push_back(u);

            if (i+1 >= n || j-1 < 0) continue;
            u = a[i][j].horiz, v = a[i+1][j-1].vert;
            if (u != -1 && v != -1) adj[u].push_back(v), adj[v].push_back(u);
            // cout << u << ' ' << v << ln;
        }
    }

    // maximum independent set in this forest
    int ans = 0;
    for (int i = 1; i < glit; i++){
        if (vis[i]) continue;
        dfs(i, -1);
        ans += max(dp[i][0], dp[i][1]);
    }

    cout << ans << ln;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

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