112E - Petya and Spiders - CodeForces Solution

#include <iostream>
#include <vector>
#include <cassert>
#include <set>
#include <tuple>
#include <climits>

using namespace std;


const int dirs[5][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {0, 0}};

int get_value(const vector<int>& v){
    int res = 0;
    for(int e: v) res = res * 2 + e;
    return res;
}

void dfs_next(int n, int index, vector<int>& state, set<tuple<int, int, int>>& res){

    if(index == n){

        vector<vector<int>> g(3, vector<int>(n, 0));
        for(int c = 0; c < n; c ++){
            int nr = 1 + dirs[state[c]][0], nc = c + dirs[state[c]][1];
            assert(0 <= nr && nr < 3 && 0 <= nc && nc < n);
            g[nr][nc] = 1;
        }

        tuple<int, int, int> tres;
        get<0>(tres) = get_value(g[0]);
        get<1>(tres) = get_value(g[1]);
        get<2>(tres) = get_value(g[2]);
        res.insert(tres);
        return;
    }

    for(int d = 0; d < 5; d ++){
        if(index == n - 1 && d == 0) continue;
        if(index == 0 && d == 2) continue;
        state[index] = d;
        dfs_next(n, index + 1, state, res);
    }
}

void get_next(int n, set<tuple<int, int, int>>& res){
    vector<int> state(n);
    dfs_next(n, 0, state, res);
}

int dfs(int n, int index, int state0, int state1,
        vector<vector<vector<int>>>& dp, const set<tuple<int, int, int>>& next){

    if(dp[index][state0][state1] != INT_MAX) return dp[index][state0][state1];

    int res = INT_MAX;
    if(index == n - 1){
        for(const tuple<int, int, int>& t: next){
            if(get<2>(t)) continue;
            int a = get<0>(t), b = get<1>(t);
            res = min(res, __builtin_popcount(a | state0) + __builtin_popcount(b | state1));
        }
    }
    else{
        for(const tuple<int, int, int>& t: next){
            int a = get<0>(t), b = get<1>(t), c = get<2>(t);
            res = min(res, __builtin_popcount(a | state0) + dfs(n, index + 1, state1 | b, c, dp, next));
        }
    }

    return dp[index][state0][state1] = res;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C; cin >> R >> C;
    if(R < C) swap(R, C); // R > C

    set<tuple<int, int, int>> next;
    get_next(C, next);

    if(R == 1){
        int res = INT_MAX;
        for(const tuple<int, int, int>& t: next){
            if(get<0>(t) || get<2>(t)) continue;
            res = min(res, __builtin_popcount(get<1>(t)));
        }
        cout << R * C - res << '\n';
        return 0;
    }

    vector<vector<vector<int>>> dp(R, vector<vector<int>>(1 << C, vector<int>(1 << C, INT_MAX)));
    int res = INT_MAX;
    for(const tuple<int, int, int>& t: next){
        if(get<0>(t)) continue;

        int state0 = get<1>(t), state1 = get<2>(t);
        res = min(res, dfs(R, 1, state0, state1, dp, next));
    }
    cout << R * C - res << '\n';

    return 0;
}