Problem:
Loading Aizu Ocean Transport Company (AOTC) accepted a new shipping order. The pieces of the cargo included in this order all have the same square footprint (2m x 2m). The cargo room has a rectangular storage space of 4m width with various longitudinal extents. Each pieces of cargo must be placed in alignment with partition boundaries which form a 1m x 1m square grid. A straddling arrangement with a neighboring partition (for example, protrusion by 50 cm) is not allowed. Neither an angled layout nor stacked placement are allowed. Note also that there may be some partitions on which any cargo loading is prohibited.   AOTC wishes to use the currently available ship for this consignment and needs to know how many pieces of cargo it can accommodate. Make a program to report the maximum cargo capacity of the cargo space given the following information: the depth (m) of the cargo space and the loading-inhibited partitions. Input The input is given in the following format.  H  N  x_1  y_1  x_2  y_2 : x_N  y_N  The first line provides the longitudinal depth H (2 ≤ H ≤ 10 4 ) of the cargo space in meters and the number of load-inhibited partitions N (0 ≤ N ≤ 4 × 10 4 ). Each of the subsequent N lines defines the position of the i -th load-inhibited partition x_i (0 ≤ x_i ≤ 3) and y_i (0 ≤ y_i ≤ H -1) in integers, where x = 0 and y = 0 indicate the bottom-left corner partition. A load-inhibited partition appears only once in the list. Output Output the maximum number of cargo pieces loaded into the cargo space. Sample Input 1 5 3
0 1
1 2
3 3 Sample Output 1 2 Input example 1 corresponds to the cargo layout shown in the left-most figure. Sample Input 2 6 4
0 2
1 3
3 4
0 5 Sample Output 2 4

Solution (Python):
h, n = map(int, input().split())
c = [set() for i in range(h + 1)]
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
c[h] = set([1, 2])
count = 0
for i in range(h - 1):
    l = c[i] | c[i + 1]
    p = None
    if l == set():
        count += 2
        c[i + 1].add(1)
        c[i + 1].add(2)
    elif 0 not in l and 1 not in l:
        p = 1
    elif 2 not in l and 3 not in l:
        p = 3
    elif 1 not in l and 2 not in l:
        p = 2
    if p:
        j = 0
        while True:
            if c[i + j + 1] | c[i + j + 1] == set():
                j += 1
            else:
                break
        if p != 2 and p - 1 not in c[i + j + 1] and p not in c[i + j + 1]:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
            continue
        if j % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
H, N = map(int, input().split())
P = [0]*H
for i in range(N):
    x, y = map(int, input().split())
    P[y] |= 1 << x

memo = [[-1]*16 for i in range(H)]
for i in range(16):
    memo[H-1][i] = 0
def dfs(i, state):
    if memo[i][state] != -1:
        return memo[i][state]
    p = P[i+1]
    s = state | p
    r = dfs(i+1, p)
    if s & 0b0011 == 0:
        r = max(r, dfs(i+1, p | 0b0011) + 1)
    if s & 0b0110 == 0:
        r = max(r, dfs(i+1, p | 0b0110) + 1)
    if s & 0b1100 == 0:
        r = max(r, dfs(i+1, p | 0b1100) + 1)
    if s & 0b1111 == 0:
        r = max(r, dfs(i+1, 0b1111) + 2)
    memo[i][state] = r
    return r
print(dfs(0, P[0]))

Solution (Python):
import sys
sys.setrecursionlimit(10002)

H, N = [int(i) for i in input().split()]
locate_put = [set(), {0, 1}, {1, 2}, {2, 3}, {0, 1, 2, 3}]
not_jama = [{0, 1, 2, 3} for _ in range(H)]
known_fn = {}

for _ in range(N):
    xi, yi = [int(i) for i in input().split()]
    not_jama[yi].remove(xi)


def get_fn(h, way_put):
    if known_fn.get((h, way_put)):
        return known_fn[(h, way_put)]
    if h == 0:
        return 0
    best_count = 0
    for way, place_put in enumerate(locate_put):
        place_can_put = not_jama[h] - locate_put[way_put] & not_jama[h - 1]
        if place_put.issubset(place_can_put):
            count = get_fn(h - 1, way)
            count += 0 if way == 0 else 1 if way != 4 else 2
            best_count = count if count > best_count else best_count
    known_fn[(h, way_put)] = best_count
    return best_count


print(get_fn(H - 1, 0))

Solution (Python):
h, n = map(int, input().split())
state_lst = [0] * h
for _ in range(n):
    x, y = map(int, input().split())
    state_lst[y] += 2 ** x

left_mask = 3
middle_mask = 6
right_mask = 12
all_mask = 15

INF = 10 ** 20
dp = [[-INF] * 2 ** 4 for _ in range(h + 1)]
dp[0][all_mask] = 0
for i in range(h):
    state = state_lst[i]
    for mask in (left_mask, middle_mask, right_mask):
        if (state & mask): continue
        for pre_state in range(16):
            if (pre_state & mask): continue
            dp[i + 1][state | mask] = max(dp[i + 1][state | mask], dp[i][pre_state] + 1)
    dp[i + 1][all_mask] = max(dp[i + 1][all_mask], -INF if state else (dp[i][0] + 2))
    dp[i + 1][state] = max(dp[i + 1][state], max(dp[i]))

print(max(dp[h]))