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("x")
	//
	//		}else{
	//			fmt.Print("o")
	//		}
	//
	//	}
	//	fmt.Println()
	//}
	fmt.Println(count)
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

int h;
int f[10000][4]={};

bool check(int bit, int shift)
{
    if(bit>>shift & 1) return false;
    if(bit>>(shift+1) & 1) return false;
    return true;
}

int dp[10000][1<<4];
int dfs(int y, int b)
{
    if(dp[y][b]>=0) return dp[y][b];
    if(y==h-1) return 0;

    int nx = 0;
    rep(i,4) nx |= f[y+1][i]<<i;
    int ret = 0;
    // 0???
    ret = max(ret, dfs(y+1,nx));
    // 1???
    rep(i,3)if(check(b,i) && check(nx,i))
    {
        int t = nx;
        t |= 1<<i;
        t |= 1<<(i+1);
        ret = max(ret, dfs(y+1,t)+1);
    }
    // 2???
    if(b==0 && nx==0) ret = max(ret, dfs(y+1,15)+2);

    return dp[y][b] = ret;
}

int main()
{
    int n;
    cin >>h >>n;
    rep(i,n)
    {
        int x,y;
        cin >>x >>y;
        f[y][x] = 1;
    }

    int s = 0;
    rep(i,4) s |= f[0][i]<<i;

    memset(dp,-1,sizeof(dp));
    cout << dfs(0,s) << endl;
    return 0;
}

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