Problem:


Score : 600 points

Problem Statement

We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.

After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

1 \leq N \leq 2000

1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_{3N}

Output

Print the maximum number of points you can gain.

Sample Input 1

2
1 2 1 2 2 1

Sample Output 1

2

Let us rearrange the five leftmost cards so that the integers written on the six cards will be 2\ 2\ 2\ 1\ 1\ 1 from left to right.

Then, remove the three leftmost cards, all of which have the same integer 2, gaining 1 point.

Now, the integers written on the remaining cards are 1\ 1\ 1.

Since these three cards have the same integer 1, we gain 1 more point.

In this way, we can gain 2 points - which is the maximum possible.

Sample Input 2

3
1 1 2 2 3 3 3 2 1

Sample Output 2

1

Sample Input 3

3
1 1 2 2 2 3 3 3 1

Sample Output 3

3



Sample input:
2
1 2 1 2 2 1


Sample output:
2

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
point=0



for t in range(N-1):
    B=A[5:]
    A=A[0:5]
    A=sorted(A)
    for s in range(3):
        if len(A)==5 and A[s]==A[s+1] and A[s+1]==A[s+2]:
            point+=1
            A.pop(s+2)
            A.pop(s+1)
            A.pop(s)
    for i in range(4):
        if len(A)==5 and A[i]==A[i+1]:
            A.pop(i+1)
            A.pop(i)
            for k in range(2):
                if len(A)==3 and A[k]==A[k+1]:
                    A.pop(k)
            if len(A)==3:
                A.pop(0)
            i=5
    if len(A)==5:
        A.pop(0)
        A.pop(0)
        A.pop(0)
    A.extend(B)
    B=[]
if A[0]==A[1] and A[1]==A[2]:
    point+=1
    
print(point)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=list(map(int,input().split()))
point=0
for t in range(N-1):
    B=A[5:]
    A=A[0:5]
    A=sorted(A)
    for s in range(3):
        if len(A)==5 and A[s]==A[s+1] and A[s+1]==A[s+2]:
            point+=1
            A.pop(s+2)
            A.pop(s+1)
            A.pop(s)
    for i in range(4):
        if len(A)==5 and A[i]==A[i+1]:
            A.pop(i+1)
            A.pop(i)
            for k in range(2):
                if len(A)==3 and A[k]==A[k+1]:
                    A.pop(k)
            if len(A)==3:
                A.pop(0)
            i=5
    if len(A)==5:
        A.pop(0)
        A.pop(0)
        A.pop(0)
    A.extend(B)
    B=[]
    print(t)
    print(A)
if A[0]==A[1] and A[1]==A[2]:
    point+=1
    
print(point)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = deque(list(map(int,input().split())))
b = [0]*n
for i in range(n):
  b[a[i]-1] += 1
x = 0
for i in range(n-1):
  c = []
  for j in range(5):
    c += [a.popleft()]
  c.sort()
  if c[0] == c[2]:
    x += 1
    b[c[0]-1] -= 3
  elif c[1] == c[3]:
    c[0],c[3] = c[3],c[0]
    x += 1
    b[c[0]-1] -= 3
  elif c[2] == c[4]:
    c.sort(reverse=True)
    x += 1
    b[c[0]-1] -= 3
  else:
    c.sort(key=lambda x:b[x-1])
    for j in range(3):
      b[c[j]-1] = -1
  a.appendleft(c.pop())
  a.appendleft(c.pop())
x += a[0]==a[2]
print(x)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
a = deque(list(map(int,input().split())))
b = [1]*n
for i in range(n-1):
  c = []
  for j in range(5):
    c += [a.popleft()]
  c.sort()
  if c[0] == c[2]:
    1
  elif c[1] == c[3]:
    c[0],c[3] = c[3],c[0]
  elif c[2] == c[4]:
    c.sort(reverse=True)
  else:
    c.sort(key=lambda x:b[x-1])
    for j in range(3):
      b[c[j]-1] = 0
  a.appendleft(c.pop())
  a.appendleft(c.pop())
print(sum(b))

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10]*n for _ in range(n)]
mx = [-10]*(n+1)
nmx = [-10]*(n+1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n-1):
    abc = aa[i*3+2:i*3+5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # b==cのときa==bになるようにする
    if b == c: a, c = c, a
    # ペアがある場合
    if a == b:
        # 得点する
        vc = dp[c][c]
        for x in range(a): chmax(c, x, dp[x][a]+1)
        for x in range(a, n): chmax(c, x, dp[a][x]+1)
        chmax(a, a, vc+1)
        # 得点しない
        chmax(a, a, mx[n])
        chmax(a, c, mx[n])
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    # 3枚とも異なる場合
    else:
        # a,b,cから2枚残す場合
        chmax(b, c, max(dp[a][a]+1, mx[n]))
        chmax(a, c, max(dp[b][b]+1, mx[n]))
        chmax(a, b, max(dp[c][c]+1, mx[n]))
        # a,b,cから1枚残す場合
        for x in range(n):
            chmax(a, x, mx[x])
            chmax(b, x, mx[x])
            chmax(c, x, mx[x])

    for x in range(n+1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)
    # print()

a = aa[-1]
ans = max(mx[n], dp[a][a]+1)+base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6)
int1 = lambda x: int(x)-1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10]*n for _ in range(n)]
mx = [-10]*(n+1)
nmx = [-10]*(n+1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n-1):
    abc = aa[i*3+2:i*3+5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # b==cのときa==bになるようにする
    if b == c: a, c = c, a
    # ペアがある場合
    if a == b:
        # 得点する
        vc = dp[c][c]
        for x in range(a): chmax(c, x, dp[x][a]+1)
        for x in range(a, n): chmax(c, x, dp[a][x]+1)
        chmax(a, a, vc+1)
        # 得点しない
        chmax(a, a, mx[n])
        chmax(a, c, mx[n])
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    # 3枚とも異なる場合
    else:
        va=dp[a][a]
        vb=dp[b][b]
        vc=dp[c][c]
        # a,b,cから2枚残す場合
        chmax(b, c, max(dp[a][a]+1, mx[n]))
        chmax(a, c, max(dp[b][b]+1, mx[n]))
        chmax(a, b, max(dp[c][c]+1, mx[n]))
        # a,b,cから1枚残す場合
        for x in range(n):
            chmax(a, x, max(mx[x],vb+1,vc+1))
            chmax(b, x, max(mx[x],va+1,vc+1))
            chmax(c, x, max(mx[x],vb+1,va+1))

    for x in range(n+1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)
    # print()

a = aa[-1]
ans = max(mx[n], dp[a][a]+1)+base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-10] * (n + 1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n - 1):
    nmx = [-10] * (n + 1)
    abc = aa[i * 3 + 2:i * 3 + 5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # b==cのときa==bになるようにする
    if b == c: a, c = c, a
    # ペアがある場合
    if a == b:
        # 得点する
        cc = dp[c][c]
        for x in range(a): chmax(c, x, dp[x][a] + 1)
        for x in range(a, n): chmax(c, x, dp[a][x] + 1)
        chmax(a, a, cc + 1)
        # 得点しない
        chmax(a, a, mx[n])
        chmax(a, c, mx[n])
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    # 3枚とも異なる場合
    else:
        # a,b,cから2枚残す場合（得点する場合を含む）
        chmax(b, c, max(dp[a][a] + 1, mx[n]))
        chmax(a, c, max(dp[b][b] + 1, mx[n]))
        chmax(a, b, max(dp[c][c] + 1, mx[n]))
        # a,b,cから1枚残す場合（得点なし）
        for x in range(n):
            chmax(a, x, mx[x])
            chmax(b, x, mx[x])
            chmax(c, x, mx[x])

    for x in range(n + 1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)
    # print()

a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-10] * (n + 1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n - 1):
    nmx = [-10] * (n + 1)
    abc = aa[i * 3 + 2:i * 3 + 5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # b==cのときa==bになるようにする
    if b == c: a, c = c, a
    # ペアがある場合
    if a == b:
        # 得点する
        for x in range(a): chmax(c, x, dp[x][a] + 1)
        for x in range(a, n): chmax(c, x, dp[a][x] + 1)
        # 得点しない
        chmax(a,a,mx[n])
        chmax(a,c,mx[n])
        for x in range(n): chmax(a, x, mx[x])
        for x in range(n): chmax(c, x, mx[x])
    # 3枚とも異なる場合
    else:
        # a,b,cから2枚残す場合（得点する場合を含む）
        chmax(b,c,max(dp[a][a]+1,mx[n]))
        chmax(a,c,max(dp[b][b]+1,mx[n]))
        chmax(a,b,max(dp[c][c]+1,mx[n]))
        # a,b,cから1枚残す場合（得点なし）
        for x in range(n):
            chmax(a, x, mx[x])
            chmax(b, x, mx[x])
            chmax(c, x, mx[x])

    for x in range(n + 1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)
    # print()

a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-10] * (n + 1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n - 1):
    nmx = [-10] * (n + 1)
    abc = aa[i * 3 + 2:i * 3 + 5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # b==cのときa==bになるようにする
    if b == c: a, c = c, a
    # a==bのときdp[c][c]が更新されてしまうのでその前にやっておく
    chmax(a, b, dp[c][c] + 1)
    # a==bのとき
    if a == b:
        for x in range(a): chmax(c, x, dp[x][a] + 1)
        for x in range(a, n): chmax(c, x, dp[a][x] + 1)
    # 手札にペアがある場合
    chmax(b, c, dp[a][a] + 1)
    chmax(a, c, dp[b][b] + 1)
    # abcのうち、1枚を残す場合
    for d in abc:
        for x in range(n):
            chmax(d, x, mx[x])

    for x in range(n + 1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)

a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-10] * (n + 1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n - 1):
    nmx = [-10] * (n + 1)
    abc = aa[i * 3 + 2:i * 3 + 5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # 1ペアできているとき
    if a == b or b == c:
        if b == c: a, c = c, a
        for x in range(a): chmax(c, x, dp[x][a] + 1)
        for x in range(a, n): chmax(c, x, dp[a][x] + 1)
    chmax(b, c, dp[a][a] + 1)
    chmax(a, c, dp[b][b] + 1)
    chmax(a, b, dp[c][c] + 1)
    for d in abc:
        for x in range(n):
            chmax(d, x, mx[x])

    for x in range(n + 1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)

a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-1] * (n + 1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n - 1):
    nmx = [-1] * (n + 1)
    abc = aa[i * 3 + 2:i * 3 + 5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # 1ペアできているとき
    if a == b or b == c:
        if b == c: a, c = c, a
        for x in range(a): chmax(c, x, dp[x][a] + 1)
        for x in range(a, n): chmax(c, x, dp[a][x] + 1)
    chmax(b, c, dp[a][a] + 1)
    chmax(a, c, dp[b][b] + 1)
    chmax(a, b, dp[c][c] + 1)
    for d in abc:
        for x in range(n):
            chmax(d, x, mx[n])

    for x in range(n + 1): mx[x] = max(mx[x], nmx[x])
    # p2D(dp)
    # print(mx)

a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #for d in DP:
    #    print(*d)
    #print()
    #print(x,y,z)
    #print()

    NLIST=[]

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,z,max(DP[i][z],DP[i][x]+1)))
                #DP[i][z]=DP[z][i]=max(DP[i][z],DP[i][x]+1)
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                NLIST.append((i,x,max(DP[i][x],DP[i][y]+1)))
                #DP[i][x]=DP[x][i]=max(DP[i][x],DP[i][y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,y,max(DP[i][y],DP[i][x]+1)))
                #DP[i][y]=DP[y][i]=max(DP[i][y],DP[i][x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    for i,j,sc in NLIST:
        DP[i][j]=DP[j][i]=max(DP[i][j],sc)

    #for d in DP:
    #    print(*d)
    #print()

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])

        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])
        NMAXDP[x]=max(NMAXDP[x],DP[i][x])
        NMAXDP[y]=max(NMAXDP[y],DP[i][y])
        NMAXDP[z]=max(NMAXDP[z],DP[i][z])

    DP[x][y]=DP[y][x]=max(DP[x][y],xy)
    DP[y][z]=DP[z][y]=max(DP[y][z],yz)
    DP[z][x]=DP[x][z]=max(DP[z][x],zx)

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#for d in DP:
#    print(*d)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

n = II()
aa = LI1()
dp = [[-10] * n for _ in range(n)]
mx = [-1] * (n + 1)
a, b = min(aa[:2]), max(aa[:2])
dp[a][b] = 0
mx[a] = mx[b] = mx[n] = 0

def chmax(i, j, val):
    if val < 0: return
    if i > j: i, j = j, i
    if val > dp[i][j]:
        dp[i][j] = val
        nmx[i] = max(nmx[i], val)
        nmx[j] = max(nmx[j], val)
        nmx[n] = max(nmx[n], val)

base = 0
for i in range(n - 1):
    nmx = [-1] * (n + 1)
    abc = aa[i * 3 + 2:i * 3 + 5]
    abc.sort()
    a, b, c = abc
    # 3枚とも同じ場合
    if a == c:
        base += 1
        continue
    # 1ペアできているとき
    if a == b or b == c:
        if b == c: a, c = c, a
        for x in range(a): chmax(c, x, dp[x][a] + 1)
        for x in range(a, n): chmax(c, x, dp[a][x] + 1)
    chmax(b, c, dp[a][a] + 1)
    chmax(a, c, dp[b][b] + 1)
    chmax(a, b, dp[c][c] + 1)
    for d in abc:
        for x in range(n):
            chmax(d, i, mx[n])

    for i in range(n + 1): mx[i] = max(mx[i], nmx[i])
    # p2D(dp)
    # print(mx)

a = aa[-1]
ans = max(mx[n], dp[a][a] + 1) + base
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #for d in DP:
    #    print(*d)
    #print()
    #print(x,y,z)
    #print()

    NLIST=[]

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,z,max(DP[i][z],DP[i][x]+1)))
                #DP[i][z]=DP[z][i]=max(DP[i][z],DP[i][x]+1)
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                NLIST.append((i,x,max(DP[i][x],DP[i][y]+1)))
                #DP[i][x]=DP[x][i]=max(DP[i][x],DP[i][y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,y,max(DP[i][y],DP[i][x]+1)))
                #DP[i][y]=DP[y][i]=max(DP[i][y],DP[i][x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    for i,j,x in NLIST:
        DP[i][j]=DP[j][i]=max(DP[i][j],x)

    #for d in DP:
    #    print(*d)
    #print()

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])

        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])
        NMAXDP[x]=max(NMAXDP[x],DP[i][x])
        NMAXDP[y]=max(NMAXDP[y],DP[i][y])
        NMAXDP[z]=max(NMAXDP[z],DP[i][z])

    DP[x][y]=xy
    DP[y][x]=xy

    DP[y][z]=yz
    DP[z][y]=yz

    DP[z][x]=zx
    DP[x][z]=zx

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#for d in DP:
#    print(*d)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #for d in DP:
    #    print(*d)
    #print()
    #print(x,y,z)
    #print()

    NLIST=[]

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,z,max(DP[i][z],DP[i][x]+1)))
                #DP[i][z]=DP[z][i]=max(DP[i][z],DP[i][x]+1)
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                NLIST.append((i,x,max(DP[i][x],DP[i][y]+1)))
                #DP[i][x]=DP[x][i]=max(DP[i][x],DP[i][y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                NLIST.append((i,y,max(DP[i][y],DP[i][x]+1)))
                #DP[i][y]=DP[y][i]=max(DP[i][y],DP[i][x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    for i,j,x in NLIST:
        DP[i][j]=DP[j][i]=x

    #for d in DP:
    #    print(*d)
    #print()

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])

        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])
        NMAXDP[x]=max(NMAXDP[x],DP[i][x])
        NMAXDP[y]=max(NMAXDP[y],DP[i][y])
        NMAXDP[z]=max(NMAXDP[z],DP[i][z])

    DP[x][y]=xy
    DP[y][x]=xy

    DP[y][z]=yz
    DP[z][y]=yz

    DP[z][x]=zx
    DP[x][z]=zx

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#for d in DP:
#    print(*d)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #for d in DP:
    #    print(*d)
    #print()
    #print(x,y,z)
    #print()

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                DP[i][z]=max(DP[i][z],DP[i][x]+1)
                DP[z][i]=max(DP[z][i],DP[i][x]+1)
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                DP[i][x]=max(DP[i][x],DP[i][y]+1)
                DP[x][i]=max(DP[x][i],DP[i][y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                DP[i][y]=max(DP[i][y],DP[i][x]+1)
                DP[y][i]=max(DP[y][i],DP[i][x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    #for d in DP:
    #    print(*d)
    #print()

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])

        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])
        NMAXDP[x]=max(NMAXDP[x],DP[i][x])
        NMAXDP[y]=max(NMAXDP[y],DP[i][y])
        NMAXDP[z]=max(NMAXDP[z],DP[i][z])

    DP[x][y]=xy
    DP[y][x]=xy

    DP[y][z]=yz
    DP[z][y]=yz

    DP[z][x]=zx
    DP[x][z]=zx

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#for d in DP:
#    print(*d)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))

ANS=0
B=[A[0],A[1]]
C=[]
D=A[-1]

for i in range(N-1):
    if A[i*3+2]==A[i*3+3]==A[i*3+4]:
        ANS+=1
    else:
        C.append((A[i*3+2],A[i*3+3],A[i*3+4]))

DP=[[-1]*(N+1) for i in range(N+1)]
MAXDP=[-1]*(N+1)

DP[B[0]][B[1]]=DP[B[1]][B[0]]=0
MAXDP[B[0]]=0
MAXDP[B[1]]=0

for x,y,z in C:
    #for d in DP:
    #    print(*d)
    #print()
    #print(x,y,z)
    #print()

    NMAXDP=[i for i in MAXDP]

    xy=max(0,DP[x][y],DP[z][z]+1)
    yz=max(0,DP[y][z],DP[x][x]+1)
    zx=max(0,DP[z][x],DP[y][y]+1)
    
    if x==y:
        for i in range(N+1):
            if DP[i][x]!=-1:
                DP[i][z]=max(DP[i][z],DP[i][x]+1)
                DP[z][i]=max(DP[z][i],DP[i][x]+1)
         
            NMAXDP[i]=max(NMAXDP[i],DP[i][z],DP[z][i])
            NMAXDP[z]=max(NMAXDP[z],DP[i][z],DP[z][i])

    if y==z:
        for i in range(N+1):
            if DP[i][y]!=-1:
                DP[i][x]=max(DP[i][x],DP[i][y]+1)
                DP[x][i]=max(DP[x][i],DP[i][y]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[x][i])
            NMAXDP[x]=max(NMAXDP[x],DP[i][x],DP[x][i])

    if z==x:
        for i in range(N+1):
            if DP[i][x]!=-1:
                DP[i][y]=max(DP[i][y],DP[i][x]+1)
                DP[y][i]=max(DP[y][i],DP[i][x]+1)
                
            NMAXDP[i]=max(NMAXDP[i],DP[i][y],DP[y][i])
            NMAXDP[y]=max(NMAXDP[y],DP[i][y],DP[y][i])

    #for d in DP:
    #    print(*d)
    #print()

    for i in range(N+1):
        DP[i][x]=DP[x][i]=max(DP[i][x],MAXDP[i])
        DP[i][y]=DP[y][i]=max(DP[i][y],MAXDP[i])
        DP[i][z]=DP[z][i]=max(DP[i][z],MAXDP[i])

        NMAXDP[i]=max(NMAXDP[i],DP[i][x],DP[i][y],DP[i][z])

    DP[x][y]=xy
    DP[y][x]=xy

    DP[y][z]=yz
    DP[z][y]=yz

    DP[z][x]=zx
    DP[x][z]=zx

    MAXDP=NMAXDP
    MAXDP[x]=max(MAXDP[x],DP[x][y],DP[y][x],DP[z][x],DP[x][z])
    MAXDP[y]=max(MAXDP[y],DP[x][y],DP[y][x],DP[z][y],DP[y][z])
    MAXDP[z]=max(MAXDP[z],DP[x][z],DP[z][x],DP[z][y],DP[y][z])

#for d in DP:
#    print(*d)

DP[D][D]+=1

DPANS=0
for d in DP:
    DPANS=max(max(d),DPANS)

print(ANS+DPANS)