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 i := 0; i < H-1; i++ {
		for j := 0; j < 3; j++ {
			if !room[i][j] && !room[i+1][j] && !room[i][j+1] && !room[i+1][j+1] {
				room[i][j] = true
				room[i+1][j] = true
				room[i][j+1] = true
				room[i+1][j+1] = true
				count++
			}
		}
	}
	fmt.Println(count)
}

C++: #include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.0000001
using namespace std;

/*
 *  state
 *
 *  0:0000
 *  1:1100
 *  2:0110
 *  3:0011
 *  4:1111
 *
 */

int main(){

	int H,N;
	scanf("%d %d",&H,&N);

	bool** check = new bool*[H];
	int** dp = new int*[H];

	for(int i = 0; i < H; i++){
		check[i] = new bool[4];
		dp[i] = new int[5];
		for(int k = 0; k < 4; k++){
			check[i][k] = true;
		}
		for(int k = 0; k < 5; k++){
			dp[i][k] = 0;
		}
	}

	int x,y;

	for(int i = 0; i < N; i++){
		scanf("%d %d",&x,&y);
		check[y][x] = false;
	}

	for(int i = 1; i <= H-1; i++){

		//from 0
		//0
		dp[i][0] = max(dp[i][0],dp[i-1][0]);
		//1
		if(check[i-1][0] == true && check[i-1][1] == true && check[i][0] == true && check[i][1] == true){
			dp[i][1] = max(dp[i][1],dp[i-1][0]+1);
		}
		//2
		if(check[i-1][1] == true && check[i-1][2] == true && check[i][1] == true && check[i][2] == true){
			dp[i][2] = max(dp[i][2],dp[i-1][0]+1);
		}
		//3
		if(check[i-1][2] == true && check[i-1][3] == true && check[i][2] == true && check[i][3] == true){
			dp[i][3] = max(dp[i][3],dp[i-1][0]+1);
		}
		//4
		if(check[i-1][0] == true && check[i-1][1] == true && check[i-1][2] == true && check[i-1][3] == true &&
				check[i][0] == true && check[i][1] == true && check[i][2] == true && check[i][3] == true){
			dp[i][4] = max(dp[i][4],dp[i-1][0]+2);
		}

		//from 1
		//0
		dp[i][0] = max(dp[i][0],dp[i-1][1]);
		//3
		if(check[i-1][2] == true && check[i-1][3] == true && check[i][2] == true && check[i][3] == true){
			dp[i][3] = max(dp[i][3],dp[i-1][1]+1);
		}

		//from 2
		//0
		dp[i][0] = max(dp[i][0],dp[i-1][2]);

		//from 3
		//0
		dp[i][0] = max(dp[i][0],dp[i-1][3]);
		//1
		if(check[i-1][0] == true && check[i-1][1] == true && check[i][0] == true && check[i][1] == true){
			dp[i][1] = max(dp[i][1],dp[i-1][0]+1);
		}

		//from 4
		//0
		dp[i][0] = max(dp[i][0],dp[i-1][4]);
	}

	int ans = 0;
	for(int i = 0; i < 5; i++)ans = max(ans,dp[H-1][i]);

	printf("%d\n",ans);

	return 0;
}

C++: #include<iostream>
#include<algorithm>
bool m[4][10010];
int dp[100010];
int main(){
	int H, N;
	std::cin >> H >> N;
	for(int i = 0; i < N; i++){
		int x, y;
		std::cin >> x >> y;
		m[x][y] = true;
	}
	for(int i = 0; i < H - 1; i++){
		int res1 = 0;
		if((!m[0][i]) && (!m[1][i]) && (!m[0][i + 1]) && (!m[1][i + 1]))res1++;
		if((!m[2][i]) && (!m[3][i]) && (!m[2][i + 1]) && (!m[3][i + 1]))res1++;
		int res2 = 0;
		if((!m[1][i]) && (!m[2][i]) && (!m[1][i + 1]) && (!m[2][i + 1]))res2++;
		dp[i] += std::max(res1, res2);
		if(res1 == 0 && res2 == 0)
			dp[i + 1] = std::max(dp[i], dp[i + 1]);
		dp[i + 2] = std::max(dp[i], dp[i + 2]);
	}
	std::cout << std::max(dp[H - 2], dp[H - 1]) << std::endl;
	return 0;
}

C++: #include<iostream>
#include<vector>
using namespace std;

using Bit = int;

int H, W = 4, N;
vector<Bit> B;

bool test(Bit b, int i) {
  return (b >> i) & 1;
}

Bit set(Bit b, int i, int j) {
  return b | (1 << i) | (1 << j);
}

bool ok(Bit u, Bit d, int i) {
  if(test(u, i) || test(u, i + 1)) return false;
  if(test(d, i) || test(d, i + 1)) return false;
  return true;
}

int dfs(int y, Bit b) {
  static vector<vector<int>> memo(H, vector<int>(1 << W, -1));
  if(~memo[y][b]) return memo[y][b];
  if(H-1 <= y) return 0;
  auto res = dfs(y+1, B[y+1]);
  for(auto i = 0; i < W-1; ++i) if(ok(b, B[y+1], i)) res = max(res, 1 + dfs(y+1, set(B[y+1], i, i+1)));
  if(ok(b, B[y+1], 0) && ok(b, B[y+1], 2)) res = max(res, 2 + dfs(y+1, 0b1111));
  return memo[y][b] = res;
}

int main() {
  cin >> H >> N;

  B.resize(H);
  for(int i = 0; i < N; ++i) {
    int x, y;
    cin >> x >> y;
    B[y] |= 1 << x;
  }

  cout << dfs(0, B[0]) << endl;
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <stack>
#include <cmath>
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
using namespace std;
//
const int inf=1e9+7;
const int mod=1e9+7;
//
struct poi{
	int X;int Y;int Z;
	bool operator<(const poi&R)const{
		return X==R.X ? Y==R.Y ? Z<R.Z : Y<R.Y : X<R.X;
	}
};
//
ll GCD(ll a,ll b){
	return (b==0)?(a):(GCD(b,a%b));
}
ll LCM(ll a,ll b){
	return a/GCD(a,b)*b;
}
//
int H,N;
int ok[10000][4];
int DP[10000][5];
int main(){
	cin>>H>>N;
	FOR(i,0,H){
		FOR(j,0,4){
			ok[i][j]=1;
		}
	}
	FOR(i,0,N){
		int X,Y;
		cin>>X>>Y;
		ok[Y][X]=0;
	}
	//
	if(ok[0][0]&&ok[0][1]&&ok[1][0]&&ok[1][1]){
		DP[0][1]=1;
	}
	if(ok[0][1]&&ok[0][2]&&ok[1][1]&&ok[1][2]){
		DP[0][2]=1;
	}
	if(ok[0][2]&&ok[0][3]&&ok[1][2]&&ok[1][3]){
		DP[0][3]=1;
	}
	if(ok[0][0]&&ok[0][1]&&ok[1][0]&&ok[1][1]&&ok[0][2]&&ok[0][3]&&ok[1][2]&&ok[1][3]){
		DP[0][4]=2;
	}
	//
	if(ok[1][0]&&ok[1][1]&&ok[2][0]&&ok[2][1]){
		DP[1][1]=1;
	}
	if(ok[1][1]&&ok[1][2]&&ok[2][1]&&ok[2][2]){
		DP[1][2]=1;
	}
	if(ok[1][2]&&ok[1][3]&&ok[2][2]&&ok[2][3]){
		DP[1][3]=1;
	}
	if(ok[1][0]&&ok[1][1]&&ok[2][0]&&ok[2][1]&&ok[1][2]&&ok[1][3]&&ok[2][2]&&ok[2][3]){
		DP[1][4]=2;
	}
	//
	FOR(i,2,H-1){
		DP[i][0]=max({DP[i-2][0],DP[i-2][1],DP[i-2][2],DP[i-2][3],DP[i-2][4]});
		DP[i][0]=max({DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3],DP[i-1][4]});
		DP[i][1]=max({DP[i-2][0],DP[i-2][1],DP[i-2][2],DP[i-2][3],DP[i-2][4]});
		DP[i][2]=max({DP[i-2][0],DP[i-2][1],DP[i-2][2],DP[i-2][3],DP[i-2][4]});
		DP[i][3]=max({DP[i-2][0],DP[i-2][1],DP[i-2][2],DP[i-2][3],DP[i-2][4]});
		DP[i][4]=max({DP[i-2][0],DP[i-2][1],DP[i-2][2],DP[i-2][3],DP[i-2][4]});
		if(ok[i][0]&&ok[i][1]&&ok[i+1][0]&&ok[i+1][1]){
			DP[i][1]++;
		}else{
			DP[i][1]=max({DP[i][1],DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3],DP[i-1][4]});
		}
		if(ok[i][1]&&ok[i][2]&&ok[i+1][1]&&ok[i+1][2]){
			DP[i][2]++;
		}else{
			DP[i][2]=max({DP[i][2],DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3],DP[i-1][4]});
		}
		if(ok[i][2]&&ok[i][3]&&ok[i+1][2]&&ok[i+1][3]){
			DP[i][3]++;
		}else{
			DP[i][3]=max({DP[i][3],DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3],DP[i-1][4]});
		}
		if(ok[i][0]&&ok[i][1]&&ok[i+1][0]&&ok[i+1][1]&&ok[i][2]&&ok[i][3]&&ok[i+1][2]&&ok[i+1][3]){
			DP[i][4]++;
		}else{
			DP[i][4]=max({DP[i][4],DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3],DP[i-1][4]});
		}
	}
	int ans=0;
	//FOR(i,0,H){
	//	FOR(j,0,5){
	//		cout<<DP[i][j]<<" ";
	//	}
	//	cout<<endl;
	//}
	FOR(i,0,5){
		ans=max(ans,DP[H-2][i]);
	}
	cout<<ans<<endl;
	return 0;
}