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

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;
}

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

using namespace std;

#define int long long
#define INF 1e9
#define LINF 1e18

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int H, N;
int no_put[10000];
int dp[2][1 << 4];

int pat[] = {0b0000, 0b0011, 0b0110, 0b1100, 0b1111};
int score[] = {0, 1, 1, 1, 2};

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> H >> N;
    for(int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        no_put[y] |= 1 << x;
    }
    int *front = dp[0];
    int *back = dp[1];
    for(int i = 0; i < (1 << 4); ++i) {
        if(i & no_put[0]) front[i] = -1;
        else front[i] = 0;
    }
    int res = 0;
    for(int i = 0; i < H - 1; ++i) {
        fill(back, back + (1 << 4), -1);
        for(int j = 0; j < (1 << 4); ++j) {
            if(front[j] == -1) continue;
            for(int k = 0; k < 5; ++k) {
                int flag1 = pat[k] & no_put[i];
                int flag2 = pat[k] & no_put[i + 1];
                if(!flag1 && !flag2 && !(j & pat[k])) {
                    int next = pat[k] | no_put[i + 1];
                    chmax(back[next], front[j] + score[k]);
                }
            }
        }
        for(int j = 0; j < (1 << 4); ++j) chmax(res, back[j]);
        int *tmp = front;
        front = back;
        back = tmp;
    }
    cout << res << endl;
    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
const int N = 256;
ll f1 = (1 << 0) + (1 << 1) + (1 << 4) + (1 << 5);
ll f2 = (1 << 1) + (1 << 2) + (1 << 5) + (1 << 6);
ll f3 = (1 << 2) + (1 << 3) + (1 << 6) + (1 << 7);
int main() {
	int h, n;
	cin >> h >> n;
	VE<VE<bool>> ban(h, VE<bool>(4, false));
	rep(i, n) {
		int x, y;
		cin >> x >> y;
		ban[y][x] = true;
	}
	// 先頭8個のみ持っておけばよいはず
	/*
	5 6 7 8
	1 2 3 4
	とする
	*/
	VVL dp(h + 1, VL(N, 0)); // i行目までで、i行目+i+1行目までの荷物の置き方を2進数で表したものの最大値
	rep(i, h - 1){
		rep(j, N) {
			// 取りうる選択の数が2*3通りしかない
			bool v1 = true, v2 = true, v3 = true;
			if (ban[i][0] || ban[i][1] || ban[i + 1][0] || ban[i + 1][1]) v1 = false;
			if (ban[i][1] || ban[i][2] || ban[i + 1][1] || ban[i + 1][2]) v2 = false;
			if (ban[i][2] || ban[i][3] || ban[i + 1][2] || ban[i + 1][3]) v3 = false;
			if (j & (1 << 0) || j & (1 << 1) || j & (1 << 4) || j & (1 << 5)) v1 = false;
			if (j & (1 << 1) || j & (1 << 2) || j & (1 << 5) || j & (1 << 6)) v2 = false;
			if (j & (1 << 2) || j & (1 << 3) || j & (1 << 6) || j & (1 << 7)) v3 = false;
			if (v1) chmax(dp[i][j + f1], dp[i][j] + 1);
			if (v2) chmax(dp[i][j + f2], dp[i][j] + 1);
			if (v3) chmax(dp[i][j + f3], dp[i][j] + 1);
			int nj = 0;
			rep(i, 4) if (j & (1 << (4 + i))) nj += (1 << i);
			chmax(dp[i + 1][nj], dp[i][j]);
		}
	}
	ll ans = 0;
	rep(i, N) chmax(ans, dp[h - 1][i]);
	rep(i, N) chmax(ans, dp[h][i]);
	cout << ans << endl;
	return 0;
}