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;
using i64 = long long;
#define rep(i,s,e) for(int (i) = (s);(i) <= (e);(i)++)
#define all(x) x.begin(),x.end()

int H,N;

int fie[10101];

i64 dp[10101][1 << 4];

int main(){
  cin >> H >> N;
  rep(i,0,N - 1){
    int x,y;
    cin >> x >> y;
    fie[y + 1] |= (1 << x);
  }
  rep(i,0,10101 - 1){
    rep(j,0,(1 << 4) - 1){
      dp[i][j] = -1e9;
    }
  }
  dp[1][fie[1]] = 0;
  rep(i,1,H - 1){
    rep(j,0,(1 << 4) - 1){
      rep(k,0,(1 << 3) - 1){
        int next = fie[i + 1];
        bool ok = true;
        int cnt = 0;
        rep(l,0,2){
          if(!(k & (1 << l))) continue;
          if(j & (3 << l)){
            ok = false;
          }
          if(next & (3 << l)){
            ok = false;
          }
          next |= (3 << l);
          cnt++;
        }
        if(!ok) continue;
        dp[i + 1][next] = max(dp[i + 1][next],dp[i][j] + cnt);
      }
    }
  }
  i64 ans = dp[H][0];
  rep(i,0,(1 << 4) - 1){
    ans = max(ans , dp[H][i]);
  }
  cout << ans << endl;
}

C++: // #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1LL << 29;
const ll LONGINF = 1LL << 60;
const ll MOD = 1000000007LL;

int board[10010][4], dp[3][1 << 8];

int main() {
    int H, N; cin >> H >> N;
    const int W = 4;
    for(int i=0; i<N; i++) {
        int x, y; cin >> y >> x;
        board[H-1-x][W-1-y] = 1;
    }

    /*
    for(int i=0; i<H; i++) {
        for(int j=0; j<W; j++) {
            cerr << board[i][j] << " ";
        }
        cerr << endl;
    }
    */

    int init_bit = 0;
    for(int i=0; i<2; i++) {
        for(int j=0; j<W; j++) {
            int k = i * 4 + j;
            init_bit |= (board[i][j] << k);
        }
    }

    fill(dp[0], dp[2], -INF);
    dp[0][init_bit] = 0;
    // cerr << bitset<8>(init_bit).to_string() << endl;
    for(int i=0; i+1<H; i++) {
        for(int j=0; j<W; j++) {
            int k = i * 4 + j;
            int cur = k % 2, nxt = 1 - cur;
            for(int bit=0; bit<(1<<8); bit++) {
                if(dp[cur][bit] == -INF) continue;
                // fprintf(stderr, "cur = %d (%d), bit = %s: dp = %d\n", cur, k, bitset<8>(bit).to_string().c_str(), dp[cur][bit]);
                chmax(dp[nxt][bit], dp[cur][bit]);
                for(int x=0; x<3; x++) {
                    bool ng = false;
                    ng |= (bit >> (4 + x + 0) & 1);
                    ng |= (bit >> (4 + x + 1) & 1);
                    ng |= (bit >> (0 + x + 0) & 1);
                    ng |= (bit >> (0 + x + 1) & 1);

                    if(ng) continue;
                    int nbit = bit;
                    nbit |= (1 << (4 + x + 0));
                    nbit |= (1 << (4 + x + 1));
                    nbit |= (1 << (0 + x + 0));
                    nbit |= (1 << (0 + x + 1));
                    chmax(dp[nxt][nbit], dp[cur][bit] + 1);
                }
                dp[cur][bit] = -INF;
            }
        }

        swap(dp[0], dp[1]);
        /*
        for(int bit=0; bit<(1<<8); bit++) {
            for(int x=0; x<2; x++) {
                if(dp[x][bit] == -INF) continue;
                fprintf(stderr, "val: x = %d, bit = %d, %d\n", x, bit, dp[x][bit]);
            }
        }
        */
        
        // 値が入っているのは常に dp[1] のほう
        // ここのインデックスを更新して dp[1] を捨てる
        int down_bit = 0;
        for(int j=0; j<W; j++) {
            down_bit |= (board[i+2][j] << j);
        }
        // cerr << "down_bit: " << bitset<4>(down_bit).to_string() << endl;

        for(int bit=0; bit<(1<<8); bit++) {
            int nbit = (bit >> 4) | (down_bit << 4);
            chmax(dp[0][nbit], dp[1][bit]);
            // if(dp[1][bit] != -INF) fprintf(stderr, "nbit = %s (%d), val = %d\n", bitset<8>(nbit).to_string().c_str(), nbit, dp[0][nbit]);
        }

        // cerr << "hi" << endl;
        /*
        for(int bit=0; bit<(1<<8); bit++) {
            if(dp[0][bit] == -INF) continue;
            fprintf(stderr, "dp[0][%d] = %d\n", bit, dp[0][bit]);
        }
        */

        fill(dp[1], dp[1] + (1 << 8), -INF);
    }

    int ans = 0;
    for(int i=0; i<(1<<8); i++) {
        chmax(ans, dp[0][i]);
    }
    cout << ans << endl;
    return 0;
}

C++: #include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int MOD = 1e9 + 7;
int flag[10000];
int main(){
	int h,n;
	cin >> h >> n;
	vector<int> x(n);
	vector<int> y(n);
	for(int i = 0; i < n; ++i)
		cin >> x[i] >> y[i];

	vector<vector<ll> > dp(h + 3, vector<ll>(1 << 4, -MOD));
	vector<vector<int> > v(h, vector<int>(4, 1));
	for(int i = 0; i < n; ++i)
		v[y[i]][x[i]] = 0;
	

	dp[0][0] = 0;
	for(int i = 0; i < h - 1; ++i){
		for(int j = 0; j < (1<<4); ++j){
			if(dp[i][j] == -MOD)
				continue;

			int d = 0;

			dp[i+1][d] = max(dp[i+1][d], dp[i][j]);

			if(~j&(1) && ~j&(1<<1) &&
				v[i+1][0] && v[i+1][1] && v[i][0] && v[i][1]
					)
				dp[i+1][d + 3] = max(1 + dp[i][j], dp[i+1][j+3]);

			if(~j&(2) && ~j&(1<<3) &&
				v[i+1][2] && v[i+1][3] && v[i][2] && v[i][3]
			  )
				dp[i+1][d + (1<<2) + (1<<3)] = max(1 + dp[i][j], dp[i+1][d + (1<<2) + (1<<3)]);

			if(~j&(2) && ~j&(1<<1) &&
				v[i+1][2] && v[i+1][1] && v[i][2] && v[i][1]
			  )
				dp[i+1][d + (1<<2) + (1<<1)] = max(1 + dp[i][j], dp[i+1][d + (1<<2) + (1<<1)]);

			bool flag = true;
			if(j==0)
			for(int k = 0; k < 4; ++k)
				for(int l = 0; l < 2; ++l)
					if(v[i+l][k]==0)
					{
						flag=false;break;}

			if(j == 0 && flag){
				dp[i+1][(1<<4)-1] = max(2 + dp[i][j], dp[i+1][(1<<4)-1]);
			}
		}
	
	}

	int j = h-1;
		ll val =0;
	for(int i = 0; i < (1<<4); ++i)
		val = max(dp[j][i], val);
		cout << val << endl;

}