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 ≤ 104) of the cargo space in meters and the number of load-inhibited partitions N (0 ≤ N ≤ 4 &times; 104). 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



Sample input:
5 3
0 1
1 2
3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
c = {i:set() for i in range(h)}
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
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 = 1
        while i + j < h:
            if c[i + j] == set():
                j += 1
            else:
                break
        if (j - 1) % 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
c = {i:set() for i in range(h)}
for i in range(n):
    a, b = map(int, input().split())
    c[b].add(a)
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 i + j + 1 < h:
            if c[i + j + 1] == set():
                j += 1
            else:
                break
        if j % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)

Submission status: Wrong Answer

Solution code:
h, n = map(int, input().split())
c = {i: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 i + j + 1 < h:
            if c[i + j + 1] == set():
                j += 1
            else:
                break
        if p != 2 and 3 - p not in c[i + j + 1] and 4 - 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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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]))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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]))

Submission status: Runtime Error

Solution code:
h, n = map(int, input().split())
c = {i: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 i + j + 1 < h:
            if c[i + j + 1] == set():
                j += 1
            else:
                break
        if p != 2 and 3 - p not in c[i + j + 2] and 4 - p not in c[i + j + 2]:
            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)

Submission status: Runtime Error

Solution code:
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 i + j + 1 < h + 1:
            if c[i + j + 1] | c[i + j + 1] == set():
                j += 1
            else:
                j += 1
                break
        if p != 2 and 3 - p not in c[i + j + 1] and 4 - p not in c[i + j + 1]:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
            continue
        if (j - 1) % 2 or j < 2:
            count += 1
            c[i + 1].add(p - 1)
            c[i + 1].add(p)
print(count)