Go: package main

import "fmt"

func main() {
	//部屋を生成
	var H int

	fmt.Scan(&H)
	room := [][4]bool{}

	for i := 0; i < H; i++ {
		room = append(room, [4]bool{})
	}

	//荷物のおけない区画を設定
	var N int
	fmt.Scan(&N)
	for i := 0; i < N; i++ {
		var x, y int
		fmt.Scan(&x, &y)
		room[y][x] = true //ものがある状態を真とする
	}
	//荷物を配置
	var count int
	for j := 0; j < H-1; j++ {
		for i := 0; i < 3; i++ {

			if !room[j][i] && !room[j+1][i] && !room[j][i+1] && !room[j+1][i+1] {
				if i!=0&&i!=2&&j!=H-3{
					if !room[j+1][i-1]&&!room[j+1][i+2]{
						if !room[j+2][0]&&!room[j+2][1]&&!room[j+2][2]&&!room[j+2][3]{
							break
						}
					}
				}
				room[j][i] = true
				room[j+1][i] = true
				room[j][i+1] = true
				room[j+1][i+1] = true
				count++
			}
		}
	}
	//for _,v:=range room{
	//	for _,v2:=range v{
	//		if !v2 {
	//			fmt.Print("◯")
	//		}else{
	//			fmt.Print("☓")
	//		}
	//	}
	//	fmt.Println()
	//}
	fmt.Println(count)
}

C++: #include <bits/stdc++.h>
using namespace std;

using ll = long long int;
using P = pair<int, int>;
using P3 = pair<int, P>;
using PP = pair<P, P>;
constexpr int INF = 1 << 30;
constexpr ll MOD = ll(1e9) + 7;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};

void chmax(int &a, int b){
    a = max(a, b);
}

bool solve(){
    int H, N;
    cin >> H >> N;
    vector<vector<bool> > ng(H,vector<bool>(4,false));
    for(int i=0;i<N;i++){
        int x, y;
        cin >> x >> y;
        ng[y][x] = true;
    }
    vector<vector<int> > dp(H*4,vector<int>(1<<4));
    int ans = 0;
    for(int i=0;i<(H-1)*4;i++){
        int y = i/4, x = i%4;
        for(int S=0;S<1<<4;S++){
            chmax(dp[i+1][S>>1], dp[i][S]);
            if(x==3) continue;
            if(ng[y][x] || ng[y][x+1] || ng[y+1][x] || ng[y+1][x+1]) continue;
            if((S&3)!=0) continue;
            chmax(dp[i+2][(S>>2)|(3<<2)],dp[i][S]+1);
        }
    }
    for(int i=0;i<H*4;i++){
        for(int S=0;S<1<<4;S++){
            chmax(ans, dp[i][S]);
        }
    }
    cout << ans << endl;
    return false;
}

int main() {
    solve();
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int MAX_H = 10101;

bool ng[MAX_H][4];
ll dp[MAX_H][1 << 4];

bool check(int y, int bit) {
    for (int x = 0; x < 4; x++) {
        if (ng[y][x] && !(bit >> x & 1)) return false; 
    }
    return true;
}

int main() {
    int h, n;
    cin >> h >> n;
    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y;
        ng[y][x] = true;
    }

    for (int i = 0; i < h - 1; i++) {
        for (int bit = 0; bit < 1 << 4; bit++) {
            if (!check(i, bit)) continue;
            for (int bit2 = 0; bit2 < 1 << 4; bit2++) {
                if (!check(i + 1, bit2)) continue;
                for (int j = 0; j < 3; j++) {
                    if (bit >> j & 1) continue;
                    if (bit >> (j + 1) & 1) continue;
                    if (bit2 >> j & 1) continue;
                    if (bit2 >> (j + 1) & 1) continue;
                    int t = bit2 | (1 << j) | (1 << (j + 1));
                    dp[i + 1][t] = max(dp[i + 1][t], dp[i][bit] + 1);
                }
                if (bit == 0 && bit2 == 0) {
                    dp[i + 1][(1 << 4) - 1] = max(dp[i + 1][(1 << 4) - 1], dp[i][0] + 2);
                }
                dp[i + 1][bit2] = max(dp[i + 1][bit2], dp[i][bit]);
            }
        }
    }
    ll ans = 0;
    for (int bit = 0; bit < 1 << 4; bit++) {
        ans = max(ans, dp[h - 1][bit]);
    }
    cout << ans << endl;
}

C++: #include <bits/stdc++.h>

using namespace std;
using LL = long long int;

const int MAX_N = 40005;

int H, N;
int X[MAX_N], Y[MAX_N];

bool hako[MAX_N][4];

int dp[MAX_N][1 << 4];

bool check(int y, int x, int S)
{
  if(x < 3 && y < H-1) {
    return !hako[y][x] && !hako[y+1][x] && !hako[y][x+1] && !hako[y+1][x+1] && !((S >> x) & 1) && !((S >> (x+1)) & 1);
  } else {
    return false;
  }
}

int main()
{
  cin >> H >> N;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  for(int i = 0; i < N; i++) {
    hako[Y[i]][X[i]] = true;
  }

  memset(dp, 0, sizeof(dp));

  for(int i = 0; i < H; i++) {
    for(int j = 0; j < (1 << 4); j++) {
      //テァツスツョテ」ツ?凝」ツ?ェテ」ツ??
      dp[i+1][0] = max(dp[i+1][0], dp[i][j]);
      //テァツスツョテ」ツ??
      if(check(i, 0, j)) {
        if(check(i,2,j)) {
          dp[i+1][(1 << 4)-1] = max(dp[i+1][(1 << 4)-1], dp[i][j]+2);
        }
        dp[i+1][(1 << 2)-1] = max(dp[i+1][(1 << 2)-1], dp[i][j]+1);
      }
      if(check(i, 1, j)) {
        dp[i+1][6] = max(dp[i+1][6], dp[i][j]+1);
      }
      if(check(i, 2, j)) {
        dp[i+1][12] = max(dp[i+1][12], dp[i][j]+1);
      }
    }
  }

  int ans = 0;
  for(int j = 0; j < (1 << 4); j++) {
    ans = max(ans, dp[H][j]);
  }
  cout << ans << endl;

  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include<bitset>

using namespace std;
#define loop(i,n) for(int i = 0; i < (n); ++i)
#define loops(i,f,n) for(int i = (f); i < (n); ++i)
#define INF 9999999
#define lint long long int
#define VEC vector<int>
#define VEC2 vector<vector<int>>

bool isObstacle[10005][4];
int dp[20005][1 << 4];



int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h, n;
	cin >> h >> n;
	loop(i, n)
	{
		int x, y;
		cin >> y >> x;
		isObstacle[h - x - 1][y] = true;
	}
	loop(i, h - 1)
	{
		loop(j, 1 << 4) {
			dp[i + 1][0] = max(dp[i + 1][0], dp[i][j]);
			loop(k, 3) {
				if (!(j >> k & 1) && !(j >> (k + 1) & 1) && !isObstacle[i][k] && !isObstacle[i][k + 1] && !isObstacle[i + 1][k] && !isObstacle[i + 1][k + 1]) {
					dp[i + 1][(1 << k) | (1 << (k + 1))] = max(dp[i + 1][(1 << k) | (1 << (k + 1))], dp[i][j] + 1);
				}
			}
			if (j == 0) {
				bool flag = true;
				loop(k, 2)
				{
					loop(t, 4) {
						if (isObstacle[i + k][t] == 1)flag = false;
					}
				}
				if (flag) {
					dp[i + 1][(1 << 4) - 1] = max(dp[i + 1][(1 << 4) - 1], dp[i][j] + 2);
				}
			}
		}
	}
	int ans = 0;
	loop(i, 1 << 4) {
		ans = max(ans, dp[h - 1][i]);
	}
	cout << ans << endl;
}

C++: #include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

std::vector<std::vector<int>> dp;
std::vector<std::string> s;
int h, n;

int check(int i, int j){
	if(s[i][j] == '#') return 0;
	if(s[i + 1][j] == '#') return 0;
	if(s[i][j + 1] == '#') return 0;
	if(s[i + 1][j + 1] == '#') return 0;
	return 1;
}

int dfs(int p, int q){
	if(p >= h - 1) return 0;
	if(~dp[p][q]) return dp[p][q];
	
	int ret = 0;
	if(q == 0){ //xxxx
		ret = std::max({dfs(p + 1, 0), dfs(p + 1, 1), dfs(p + 1, 2), dfs(p + 1, 3), dfs(p + 1, 4)});
	}else if(q == 1){ //ooxx
		int count = check(p, 0);
		ret = std::max(count + dfs(p + 1, 0), count + dfs(p + 1, 3));
	}else if(q == 2){ //xoox
		int count = check(p, 1);
		ret = count + dfs(p + 1, 0);
	}else if(q == 3){ //xxoo
		int count = check(p, 2);
		ret = std::max(count + dfs(p + 1, 0), count + dfs(p + 1, 1));
	}else if(q == 4){ //oooo
		int count = check(p, 0) + check(p, 2);
		ret = count + dfs(p + 1, 0);
	}
	
	return dp[p][q] = ret;
}

int main(){
	cin >> h >> n; s.resize(h, std::string(4, '.'));
	for(int i = 0; i < n; i++){
		int a, b; cin >> a >> b;
		
		s[b][a] = '#';
	}
	reverse(begin(s), end(s));
	dp.resize(h - 1, std::vector<int>(5, -1));
	
	cout << std::max({dfs(0, 0), dfs(0, 1), dfs(0, 2), dfs(0, 3), dfs(0, 4)}) << endl;
	return 0;
}