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;
typedef long long ll;
#define _overload4(_1,_2,_3,_4,name,...) name
#define _overload3(_1,_2,_3,name,...) name
#define _overload2(_1,_2,name,...) name
#define _re(n) _rep(i,n)
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(ll i=a;i<b;++i)
#define _repc(i,a,b,c) for(ll i=a;i<b;i+=c)
#define rep(...) _overload4(__VA_ARGS__,_repc,_repi,_rep,_re)(__VA_ARGS__)
#define _rre(n) _rrep(i,n)
#define _rrep(i,n) _rrepi(i,0,n)
#define _rrepi(i,a,b) for(ll i=b-1;i>=a;i--)
#define _rrepc(i,a,b,c) for(ll i=a+(b-a-1)/c*c;i>=a;i-=c)
#define rrep(...) _overload4(__VA_ARGS__,_rrepc,_rrepi,_rrep,_rre)(__VA_ARGS__)
#define sum(...) accumulate(range(__VA_ARGS__),0)
#define _range(i) (i).begin(),(i).end()
#define _rangek(i,k) (i).begin(),(i).begin()+k
#define range(...) _overload2(__VA_ARGS__,_rangek,_range)(__VA_ARGS__)
#define LINF (ll)1000000000000000000
#define MOD (ll)1000000007
#define INF (int)1000000007
#define Yes(i) out(i?"Yes":"No")
#define YES(i) out(i?"YES":"NO")
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define CHR(...) char __VA_ARGS__;in(__VA_ARGS__)
#define DBL(...) double __VA_ARGS__;in(__VA_ARGS__)
#define vec(type,name,size) vector<type> name(size);
#define VEC(type,name,size) vector<type> name(size);in(name)
struct aaa{aaa(){cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}aaaaaaa;
inline void in() {}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec);
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p);
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec);
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p);
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<typename T,typename L>
istream& operator >> (istream& is, pair<T,L>& p){is >> p.first;is >> p.second;return is;}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){os << vec[0];rep(i,1,vec.size()){os << ' ' << vec[i];}return os;}
template<typename T,typename L>
ostream& operator << (ostream& os, pair<T,L>& p){os << p.first << " " << p.second;return os;}
template <class Head, class... Tail>
inline void in(Head&& head,Tail&&... tail){cin>>head;in(move(tail)...);}
template <class T>
inline void out(T t){cout<<t<<'\n';}
inline void out(){cout<<'\n';}
template <class Head, class... Tail>
inline void out(Head head,Tail... tail){cout<<head<<' ';out(move(tail)...);}


int main(){
    INT(h,n);
    vector<vector<bool>>a(4,vector<bool>(h));
    rep(n){
        INT(x,y);
        a[x][y]=1;
    }
    int ans=0;
    rep(i,1,h-1){
        bool a1=a[0][i-1]||a[0][i]||a[1][i-1]||a[1][i];
        bool a2=a[2][i-1]||a[2][i]||a[1][i-1]||a[1][i];
        bool a3=a[2][i-1]||a[2][i]||a[3][i-1]||a[3][i];
        bool b1=a[0][i+1]||a[0][i]||a[1][i+1]||a[1][i];
        bool b3=a[2][i+1]||a[2][i]||a[3][i+1]||a[3][i];
        if(a1&&a2&&a3)continue;
        if(a1&&a2){
            ans++;
            a[2][i-1]=a[2][i]=a[3][i-1]=a[3][i]=1;
        }else if(a3&&a2){
            ans++;
            a[0][i-1]=a[0][i]=a[1][i-1]=a[1][i]=1;
        }else if(a1&&a3){
            if(b1||b3){
                ans++;
                a[2][i-1]=a[2][i]=a[1][i-1]=a[1][i]=1;
            }
        }else if(a1){
            ans++;
            a[2][i-1]=a[2][i]=a[3][i-1]=a[3][i]=1;
        }else if(a3){
            ans++;
            a[0][i-1]=a[0][i]=a[1][i-1]=a[1][i]=1;
        }else{
            ans+=2;
            a[2][i-1]=a[2][i]=a[3][i-1]=a[3][i]=1;
            a[0][i-1]=a[0][i]=a[1][i-1]=a[1][i]=1;
        }
    }
    rep(i,0,3)if(!(a[i][h-2]||a[i][h-1]||a[i+1][h-1]||a[i+1][h-2])){
        a[i][h-2]=a[i][h-1]=a[i+1][h-1]=a[i+1][h-2]=1;
        ans++;
    }
    out(ans);
}

C++: /*#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x,y,H,N,cnt=0;
int main(void){
	cin>>H;
	int a[H][4];
	cin>>N;
	for(int i=0;i<H;i++){
		for(int j=0;j<4;j++){
			a[i][j]=0;
		}
		//cout<<endl;
	}
	for(int i=0;i<N;i++){
		cin>>x>>y;
		a[x][y]=1;
	}
	for(int i=0;i<H-1;i++){
		for(int j=0;j<4-1;j++){
			if(1>a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1])
			{
				cnt++;
				//cout<<i<<" "<<j<<endl;
				a[i][j]=a[i][j+1]=a[i+1][j]=a[i+1][j+1]=1;
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
}*/
#include<bits/stdc++.h>
using namespace std;
int H,N;
int t[100005][4];
int dp[100005][1<<4];

int main(){
	cin>>H>>N;
	for(int i=0;i<N;i++){
		int x,y;
		cin>>x>>y;
		t[y][x]=1;
	}
	
	for(int i=0;i<H;i++)
		for(int j=0;j<(1<<4);j++)
			dp[i][j]=-100000000;
	dp[0][0]=0;
	int ans=0;
	
	for(int i=0;i<H;i++){
		for(int b=0;b<(1<<4);b++){
			
			ans=max(ans,dp[i][b]);
			if(i==H-1)continue;
			
			int tmp[2][4]={};
			
			for(int j=0;j<4;j++){
				tmp[0][j]=t[i][j];
				tmp[1][j]=t[i+1][j];
				tmp[0][j]|=(b>>j&1);
			}
			dp[i+1][0]=max(dp[i+1][0],dp[i][b]);
			
			if(!tmp[0][0]&&!tmp[0][1]&&!tmp[1][0]&&!tmp[1][1]){
				dp[i+1][3]=max(dp[i+1][3],dp[i][b]+1);
			}
			if(!tmp[0][1]&&!tmp[0][2]&&!tmp[1][1]&&!tmp[1][2]){
				dp[i+1][6]=max(dp[i+1][6],dp[i][b]+1);
			}
			if(!tmp[0][2]&&!tmp[0][3]&&!tmp[1][2]&&!tmp[1][3]){
				dp[i+1][12]=max(dp[i+1][12],dp[i][b]+1);
			}
			if(!tmp[0][0]&&!tmp[0][1]&&!tmp[1][0]&&!tmp[1][1]){
				if(!tmp[0][2]&&!tmp[0][3]&&!tmp[1][2]&&!tmp[1][3]){
					dp[i+1][15]=max(dp[i+1][15],dp[i][b]+2);
				}
			}
			
		}
		
	}
	cout<<ans<<endl;
	return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
int h,n,dp[10001][1<<4],x,y,ans,t,maxval,cnt;
bool a[10001][4];
void dul(int i,int inc){
	maxval=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+inc][j]=max(dp[i+inc][j],max(dp[i][j],maxval));
	}
}
void case2(int i){
	cnt=0;
	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;
	}
}
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++){
		dul(i,0);
		case2(i);
		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);
							}
						}
						dp[i+1][p]=max(dp[i+1][p],dp[i][j]+1);
					}
				}
			}
		}
		dul(i,1);
	}
	for(int i=0;i<(1<<4);i++)
		ans=max(ans,dp[h-1][i]);
	cout<<ans<<endl;
}

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

int obs[10005];
int dp[10005][16];
int mask[5]={0, 3, 6, 12, 15};
int cnt[5] ={0, 1, 1, 1,  2};
int main() {
  int h, n;
  cin >> h >> n;
  fill(obs, obs+10005, 0);
  for(int i=0; i<n; i++){
    int x, y;
    cin >> x >> y;
    obs[y]=obs[y] | (1<<x);
  }
  obs[h]=15;
  fill(dp[h], dp[h]+16, 0);
  for(int i=h-1; i>=0; i--){
    for(int j=0; j<16; j++){
      dp[i][j]=0;
      for(int k=0; k<5; k++){
        if((mask[k]&j)|(mask[k]&obs[i+1])) continue;
        dp[i][j]=max(dp[i][j], 
             cnt[k]+dp[i+1][obs[i+1]|mask[k]]);
      }
    }
  }
  cout << dp[0][obs[0]] << endl;
}