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 <bits/stdc++.h>

using namespace std;

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

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, P> Pi;
typedef pair<P, P> PP;

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

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 located[100000];
int dp[2][1 << 4];
int down[5] = {0b0000, 0b0011, 0b0110, 0b1100, 0b1111};
int score[5] = {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;
        located[y] |= (1 << x);
    }
    int *now = dp[0];
    int *next = dp[1];
    for(int i = 0; i < (1 << 4); ++i) {
        if(i & located[0]) now[i] = -1;
        else now[i] = 0;
    }
    int res = 0;
    for(int i = 0; i < H - 1; ++i) {
        fill(next, next + (1 << 4), -1);
        for(int j = 0; j < (1 << 4); ++j) {
            if(now[j] == -1) continue;
            for(int k = 0; k < 5; ++k) {
                int front = down[k] & located[i];
                int back = down[k] & located[i + 1];
                if(front || back || j & down[k]) continue;
                int next_put = down[k] | located[i + 1];
                next[next_put] = max(next[next_put], now[j] + score[k]);
            }
        }
        for(int i = 0; i < (1 << 4); ++i) chmax(res, next[i]);
        int *temp = now;
        now = next;
        next = temp;
    }
    cout << res << endl;
	return 0;
}

C++: #include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

vector<vector<int>>use_v = {
	{0,0,0,0},
	{1,1,0,0},
	{0,1,1,0},
	{0,0,1,1},
	{1,1,1,1}
};

int main() {	
	int H,N;cin>>H>>N;
	vector<vector<int>>obs(H,vector<int>(4));
	for (int i = 0; i < N; ++i) {
		int x,y;cin>>x>>y;
		obs[y][x]=true;
	}

	vector<vector<int>>dp(H,vector<int>(5));
	dp[0][0]=0;

	for (int u = 0; u < H-1; ++u) {
		for (int now_use_id = 0; now_use_id < 5; ++now_use_id) {
			for (int next_use_id = 0; next_use_id < 5; ++next_use_id) {
				vector<int>now_use_v(use_v[now_use_id]);
				vector<int>next_use_v(use_v[next_use_id]);
				bool ok=true;
				for (int i = 0; i < 4; ++i) {
					if (now_use_v[i] && next_use_v[i]) {
						ok=false;
					}
				}
				for (int y = u; y < u + 2; ++y) {
					for (int x = 0; x < 4; ++x) {
						if (next_use_v[x] && obs[y][x]) {
							ok=false;
						}
					}
				}
				int plus=(next_use_id+2)/3;
				if (ok) {
					dp[u+1][next_use_id]=max(dp[u+1][next_use_id],dp[u][now_use_id]+plus);
				}
			}
		}
	}
	int ans=0;
	ans=*max_element(dp[H-1].begin(),dp[H-1].end());
	cout<<ans<<endl;
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int main(void){
	int h,n;
	int x,y;
	int now,next;
	int box[10001][4];
	int dp[10001][16];
	int msk2[4]={1,2,4,8};
	int msk[4]={3,6,12,15};
	int i,j,k;
	int a,b;
	int MAX;
	cin>>h>>n;
	for(i=0;i<h;i++){
		for(j=0;j<4;j++){
			box[i][j]=0;
		}
	}
	for(i=0;i<n;i++){
		cin>>x>>y;
		box[y][x]++;
	}
	for(i=0;i<h;i++){
		for(j=0;j<16;j++){
			dp[i][j]=0;
		}
	}
	for(i=0;i<h-1;i++){
		for(j=0;j<16;j++){
			now=0;	next=0;
			for(k=0;k<4;k++){
				now+=box[i][k]*msk2[k];
				next+=box[i+1][k]*msk2[k];
			}
			now|=j;
			//cout<<"NOW="<<now<<" "<<"NEXT="<<next<<endl;
			for(k=0;k<16;k++)	dp[i+1][k]=max(dp[i+1][k],dp[i][j]);
			for(k=0;k<4;k++){
				a=now&msk[k];
				b=next&msk[k];
				//cout<<"A="<<a<<" "<<"B="<<b<<endl;
				if((now&msk[k])==0){
					if((next&msk[k])==0){
						//cout<<"YEAR"<<endl;
						if(k==3)	dp[i+1][next|msk[k]]=max(dp[i+1][next],dp[i][now]+2);
						else		dp[i+1][next|msk[k]]=max(dp[i+1][next],dp[i][now]+1);
					}
				}
			}
		}
	}
	// for(i=0;i<h;i++){
		// for(j=0;j<4;j++){
			// if(j)	cout<<" ";
			// cout<<box[i][j];
		// }
		// cout<<endl;
	// }
	// cout<<endl;
	// for(i=0;i<h;i++){
		// cout<<"I="<<i<<" ";
		// for(j=0;j<16;j++){
			// if(j)	cout<<" ";
			// cout<<dp[i][j];
		// }
		// cout<<endl;
	// }
	MAX=INT_MIN;
	for(i=0;i<16;i++)	MAX=max(MAX,dp[h-1][i]);
	cout<<MAX<<endl;
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>

const int MAX_RC = 30000;
int R, N;
const int K = 4;
bool grid[MAX_RC][K];
int cache[MAX_RC][1 << K];

int genbits(int r) {
  int a = grid[r][0] ? 1 : 0;
  int b = grid[r][1] ? 2 : 0;
  int c = grid[r][2] ? 4 : 0;
  int d = grid[r][3] ? 8 : 0;
  return a | b | c | d;
}


int dp(int r, int bits) {
  if (r == R - 1) return 0;
  if (cache[r][bits] != -1) return cache[r][bits];
  int max = 0;
  for (int i = 0; i < K - 1; ++i) {
    if (!(bits & (1 << i)) && !(bits & (1 << (i + 1))) && !grid[r][i] && !grid[r][i + 1] && !grid[r + 1][i] && !grid[r + 1][i + 1]) {
      max = std::max(max, dp(r + 1, (1 << i) | (1 << (i + 1))) + 1);
    }
  }
  if (genbits(r) == 0 && genbits(r + 1) == 0) {
    max = std::max(max, dp(r + 2, 0) + 2);
  }
  max = std::max(max, dp(r + 1, 0));
  cache[r][bits] = max;
  return max;
}

int main() {
  memset(cache, -1, sizeof(cache));
  scanf("%d %d", &R, &N);
  for (int i = 0; i < N; ++i) {
    int x, y;
    scanf("%d %d", &x, &y);
    grid[y][x] = 1;
  }
  printf("%d\n", dp(0, 0));
}

C++: #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)

int H,N;

vector<int> fie;

vector<vector<int>> dp;

int dfs(int h,int state){
    if(h == H) return 0;
    if(dp[h][state] != -1) return dp[h][state];

    int ans = dfs(h + 1,fie[h]);

    for(int i = 0;i < 3;i++){
        if((state >> i) & 3) continue;
        if((fie[h] >> i) & 3) continue;
        ans = max(ans , dfs(h + 1,fie[h] | (3 << i)) + 1);
    }

    if(state == 0 && fie[h] == 0){
        ans = max(ans , dfs(h + 1,(1 << 4) - 1) + 2);
    }

    return dp[h][state] = ans;
}

int main(){
    cin >> H >> N;
    fie.resize(H);
    dp.resize(H,vector<int>((1 << 4),-1));
    rep(i,0,N - 1){
        int x,y;
        cin >> x >> y;
        fie[y] |= (1 << x);
    }

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

C++: #include <bits/stdc++.h>
using namespace std;
int h,n,dp[10001][1<<4],x,y,ans,t;
bool a[10001][4];
int main(){
	cin>>h>>n;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		a[y][x]=1;
	}
	for(int i=0;i<h-1;i++){
		int maxval=0,cnt=0,c=0;
		for(int j=0;j<(1<<4);j++)
			maxval=max(maxval,dp[i-1][j]);
		if(i){
			for(int j=0;j<(1<<4);j++)
				dp[i][j]=max(dp[i][j],max(dp[i][j],maxval));
		}
		for(int j=0;j<4;j++)
			if(!a[i][j]&&!a[i+1][j])cnt++;
		if(cnt==4){
			dp[i+1][(1<<4)-1]=dp[i][0]+2;
		}
		for(int j=0;j<(1<<4);j++){
			for(int k=0;k<3;k++){
				if(!((j>>k)&1)&&!((j>>(k+1))&1)&&!a[i][k]&&!a[i][k+1]){
					if(!a[i+1][k]&&!a[i+1][k+1]){
						int p=0;
						for(int l=0;l<4;l++){
							if(a[i+1][l]||l==k||l==k+1){
								p+=(1<<l);
							}
							if(!i)cout<<p<<endl;
						}
						dp[i+1][p]=max(dp[i+1][p],dp[i][j]+1);
						if(p==(1<<4)-1)c++;
					}
				}
			}
		}
		maxval=cnt=0;
		for(int j=0;j<(1<<4);j++)
			maxval=max(maxval,dp[i-1][j]);
		if(i){
			for(int j=0;j<(1<<4);j++)
				dp[i+1][j]=max(dp[i+1][j],max(dp[i][j],maxval));
		}
	}
	for(int i=0;i<h;i++){
		for(int j=0;j<(1<<4);j++)
			cout<<dp[i][j]<<' ';
		cout<<endl;
	}
	for(int i=0;i<(1<<4);i++)
		ans=max(ans,dp[h-1][i]);
	cout<<ans<<endl;
}