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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-2):
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
    continue
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
    continue
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
    continue
  dp[b][c] = dp[a][a] + 1
  dp[a][c] = dp[b][b] + 1
  dp[a][b] = dp[c][c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b])
  dp[a][b] = dpmax
  dp[b][c] = dpmax
  dp[a][c] = dpmax
  for j in range(N):
    dp[j][a] = dpmaxk[j]
    dp[j][b] = dpmaxk[j]
    dp[j][c] = dpmaxk[j]
    dp[a][j] = dpmaxl[j]
    dp[b][j] = dpmaxl[j]
    dp[c][j] = dpmaxl[j]

z = A[-1]-1
print(max(dpmax,dp[z][z]+1)+score)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-2):
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
  dp[b][c] = dp[a][a] + 1
  dp[a][c] = dp[b][b] + 1
  dp[a][b] = dp[c][c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b])
  dp[a][b] = dpmax
  dp[b][c] = dpmax
  dp[a][c] = dpmax
  for i in range(N):
    dp[i][a] = dpmaxk[i]
    dp[i][b] = dpmaxk[i]
    dp[i][c] = dpmaxk[i]
    dp[a][i] = dpmaxl[i]
    dp[b][i] = dpmaxl[i]
    dp[c][i] = dpmaxl[i]

z = A[-1]-1
print(max(dpmax,dp[z][z]+1)+score)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])
a -= 1
b -= 1
c -= 1
d -= 1
e -= 1

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-2):
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
    continue
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
    continue
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
    continue
  dp[b][c] = dp[a][a] + 1
  dp[a][c] = dp[b][b] + 1
  dp[a][b] = dp[c][c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b])
  dp[a][b] = dpmax
  dp[b][c] = dpmax
  dp[a][c] = dpmax
  for i in range(N):
    dp[i][a] = dpmaxk[i]
    dp[i][b] = dpmaxk[i]
    dp[i][c] = dpmaxk[i]
    dp[a][i] = dpmaxl[i]
    dp[b][i] = dpmaxl[i]
    dp[c][i] = dpmaxl[i]

z = A[-1]-1
print(max(dpmax,dp[z][z]+1)+score)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N = I()
A = IL()

dp = [[0 for j in range(N)] for i in range(N)]
dpmax = 0
dpmaxk = [0 for i in range(N)]
dpmaxl = [0 for i in range(N)]
score = 0
a,b,c,d,e = sorted(A[:5])

if a == b == c:
  dp[d][e] = 1
  dp[e][d] = 1
elif b == c == d:
  dp[a][e] = 1
  dp[e][a] = 1
elif c == d == e:
  dp[a][b] = 1
  dp[b][a] = 1

for i in range(N-2):
  a,b,c = A[i*3+5:i*3+8]
  a -= 1
  b -= 1
  c -= 1
  if a == b == c:
    score += 1
    continue
  elif a == b:
    for k in range(N):
      dp[k][c] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][c])
      dpmaxk[k] = max(dpmaxk[k],dp[k][c])
      dpmaxl[c] = max(dpmaxl[c],dp[k][c])
    continue
  elif a == c:
    for k in range(N):
      dp[k][b] = max(dp[k][a],dp[a][k]) + 1
      dpmax = max(dpmax,dp[k][b])
      dpmaxk[k] = max(dpmaxk[k],dp[k][b])
      dpmaxl[b] = max(dpmaxl[b],dp[k][b])
    continue
  elif b == c:
    for k in range(N):
      dp[k][a] = max(dp[k][b],dp[b][k]) + 1
      dpmax = max(dpmax,dp[k][a])
      dpmaxk[k] = max(dpmaxk[k],dp[k][a])
      dpmaxl[a] = max(dpmaxl[a],dp[k][a])
    continue
  dp[b][c] = dp[a][a] + 1
  dp[a][c] = dp[b][b] + 1
  dp[a][b] = dp[c][c] + 1
  dpmax = max(dpmax,dp[b][c],dp[a][c],dp[a][b])
  dpmaxk[b] = max(dpmaxk[b],dp[b][c])
  dpmaxl[c] = max(dpmaxl[c],dp[b][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][c])
  dpmaxl[c] = max(dpmaxl[c],dp[a][c])
  dpmaxk[a] = max(dpmaxk[a],dp[a][b])
  dpmaxl[b] = max(dpmaxl[b],dp[a][b])
  dp[a][b] = dpmax
  dp[b][c] = dpmax
  dp[a][c] = dpmax
  for i in range(N):
    dp[i][a] = dpmaxk[i]
    dp[i][b] = dpmaxk[i]
    dp[i][c] = dpmaxk[i]
    dp[a][i] = dpmaxl[i]
    dp[b][i] = dpmaxl[i]
    dp[c][i] = dpmaxl[i]
  
z = A[-1]-1
print(max(dpmax,dp[z][z]+1)+score)

Submission status: Runtime Error

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

def get_point(ind, arr):
  ans = 0
  data = {}
  for i in range(ind,ind+5):
    if arr[i] in data:
      data[arr[i]] += 1
    else:
      data[arr[i]] = 1
  data_max = max(data.value())
  if data_max >= 3:
    ans = 1
  return ans
def check(ind, arr):
  ans = 0
  data = {}
  for i in range(ind,ind+5):
    if arr[i] in data:
      data[arr[i]] += 1
    else:
      data[arr[i]] = 1
  data_max = max(data.value())
  if data_max >= 3:
    ans = 1
    for datum in data:
      if data[datum] == data_max:
        ind_tmp = ind
        for i in range(ind,ind+5):
          if arr[ind] == datum:
            arr[ind], arr[ind_tmp] = drr[ind_tmp], arr[ind]
            ind_tmp += 1
  else:
    nxt1 = A[ind+5]
    nxt2 = A[ind+6]
    nxt3 = A[ind+7]
    
    cut1 = ind
    cut2 = ind+1
    cut3 = ind+2
    for i in range(ind, ind+5):
      for j in range(i+1, ind+5):
        now1 = A[i]
        now2 = A[j]
        if get_point(0, [now1, now2, nxt1, nxt2, nxt3]):
          remain = list()
          for k in range(ind, ind+5):
            if not( k == i or k == j):
              remain.append(k)
          cut1 = remain[0]
          cut2 = remain[1]
          cut3 = remain[2]
        
        arr[ind], arr[cut1] = arr[cut1], arr[ind]
        arr[ind+1], arr[cut2], arr[cut2], arr[ind+1]
        arr[ind+2], arr[cut3] = arr[cut3], arr[ind+2]
          
         
    
  return ans

ind = 0
ans = 0
for _ in range(N-1):
  ans += check(ind, A)
  ind += 3

if A[ind] == A[ind+1] and A[ind+1] == A[ind+2]:
  ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def calc(b, c, M):
    for j in range(1, n+1):
        dp[j][c] = max(dp[j][c], dp[j][b] + 1, dp[b][j] + 1)
        dp[c][j] = max(dp[c][j], dp[j][b] + 1, dp[b][j] + 1)
        M = max(M, dp[j][c], dp[c][j])
    return M

n = I()
a = LI()
# dp[i][j][k] = i回目まで操作したとき一番左の数がjで一番右の数がkであるときの最大値
dp = [[-inf] * (n+1) for _ in range(n+1)]
dp[a[0]][a[1]] = 0
tmp = 0
M = 0
for i in range(1, n):
    a1, a2, a3 = a[3*i-1], a[3*i], a[3*i+1]
    if a1 == a2 and a2 == a3:
        tmp += 1
        continue
    if a1 == a2:
        b = a1
        c = a3
        new_M = calc(b, c, M)
    elif a2 == a3:
        b = a2
        c = a1
        new_M = calc(b, c, M)
    elif a3 == a1:
        b = a3
        c = a2
        new_M = calc(b, c, M)
    dp[a1][a2] = max(dp[a1][a2], M)
    dp[a2][a1] = max(dp[a2][a1], M)
    dp[a2][a3] = max(dp[a2][a3], M)
    dp[a3][a2] = max(dp[a3][a2], M)
    dp[a3][a1] = max(dp[a3][a1], M)
    dp[a1][a3] = max(dp[a1][a3], M)
    M = new_M

a_last = a[-1]
ans = dp[a_last][a_last] + 1
for i in range(1, n+1):
    for j in range(1, n+1):
        ans = max(ans, dp[i][j])
ans += tmp
print(ans)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=[[-1]*(N+1)for _ in range(N+1)]
M=0
r=[-1]*(N+1)
def c(i,j,k):
    D[i][j]=max(k,D[i][j])
    D[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
A[0]=X
A[1]=Y
D[X][Y]=0
D[Y][X]=0
r[X]=0
r[Y]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in C:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
I=2*N
D=[[-I]*(N+1)for _ in range(N+1)]
M=0
r=[-I]*(N+1)
def c(i,j,k):
    DP[i][j]=max(k,D[i][j])
    DP[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
D[A[0]][A[1]]=0
D[A[1]][A[0]]=0
r[A[0]]=0
r[A[1]]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in C:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
I=2*N
D=[[-I]*(N+1)for _ in range(N+1)]
M=0
r=[-I]*(N+1)
def c(i,j,k):
    DP[i][j]=max(k,D[i][j])
    DP[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
D[A[0]][A[1]]=0
D[A[1]][A[0]]=0
r[A[0]]=0
r[A[1]]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in change:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
I=2*N
D=[[-INF]*(N+1)for _ in range(N+1)]
M=0
r=[-INF]*(N+1)
def c(i,j,k):
    DP[i][j]=max(k,D[i][j])
    DP[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
D[A[0]][A[1]]=0
D[A[1]][A[0]]=0
r[A[0]]=0
r[A[1]]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in change:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-5] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(ma, X[a2][a2] + 1), max(ma, X[a1][a1] + 1)
        X[a2] = [max(x, m) for j in zip(X[a2], MA)]
        MA = [max(m, x1, x2) for m, x1, x2 in zip(MA, X[a1], X[a2])]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(ma, X[c][c] + 1), max(ma, X[b][b] + 1), max(ma, X[a][a] + 1)
        X[a] = [max(x, m) for x, m in zip(X[a], MA)]
        X[b] = [max(x, m) for x, m in zip(X[b], MA)]
        X[c] = [max(x, m) for x, m in zip(X[c], MA)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(m, xa, xb, xc) for m, xa, xb, xc in zip(MA, X[a], X[b], X[c])]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))