Problem:


Score : 400 points

Problem Statement

There is a grid with N rows and N columns of squares. Let (i,j) be the square at the i-th row from the top and the j-th column from the left.

These squares have to be painted in one of the C colors from Color 1 to Color C. Initially, (i,j) is painted in Color c_{i,j}.

We say the grid is a good grid when the following condition is met for all i,j,x,y satisfying 1 \leq i,j,x,y \leq N:

If (i+j) \% 3=(x+y) \% 3, the color of (i,j) and the color of (x,y) are the same.

If (i+j) \%  3 \neq (x+y) \% 3, the color of (i,j) and the color of (x,y) are different.

Here, X \% Y represents X modulo Y.

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is X before repainting and Y after repainting, is D_{X,Y}.

Find the minimum possible sum of the wrongness of all the squares.

Constraints

1 \leq N \leq 500

3 \leq C \leq 30

1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)

1 \leq c_{i,j} \leq C

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N C
D_{1,1} ... D_{1,C}
:
D_{C,1} ... D_{C,C}
c_{1,1} ... c_{1,N}
:
c_{N,1} ... c_{N,N}

Output

If the minimum possible sum of the wrongness of all the squares is x, print x.

Sample Input 1

2 3
0 1 1
1 0 1
1 4 0
1 2
3 3

Sample Output 1

3

Repaint (1,1) to Color 2. The wrongness of (1,1) becomes D_{1,2}=1.

Repaint (1,2) to Color 3. The wrongness of (1,2) becomes D_{2,3}=1.

Repaint (2,2) to Color 1. The wrongness of (2,2) becomes D_{3,1}=1.

In this case, the sum of the wrongness of all the squares is 3.

Note that D_{i,j} \neq D_{j,i} is possible.

Sample Input 2

4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2

Sample Output 2

428



Sample input:
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3


Sample output:
3

Submission status: Time Limit Exceeded

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

D = [None] * C
P = [None] * N

Q = [[[None for y in range(N)] for x in range(N)] for c in range(C)] # Q[c][x][y]

for i in range(C):
    D[i] = list(map(int, input().split())) #D[c_before][c_after]

for i in range(N):
    P[i] = list(map(int, input().split())) #P[x][y] = c+1

for c in range(C):
    for x in range(N):
        for y in range(N):
            Q[c][x][y] = D[P[x][y]-1][c]

R = []

for c0 in range(C):
    for c1 in range(C):
        if c0 == c1:
            continue
        for c2 in range(C):
            if c0 == c2 or c1 == c2:
                continue
            R.append([Q[c0][x][y] if (x + y) % 3 == 0 else Q[c1][x][y] if (x + y) % 3 == 1 else Q[c2][x][y] for x in range(N) for y in range(N)])

print(min([sum(r) for r in R]))

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, C = list(map(int, input().split()))
D =[list(map(int, input().split())) for _ in range(C)] 

remains = {0: [], 1: [], 2: []} 
for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3].append(line[j])

INF = 65535

def recolor(x, y): 
    return D[x-1][y-1]

answer = INF 
for choice in permutations(range(1, C+1), 3): 
    _answer = 0 
    for i, c in enumerate(choice):
        _answer += sum([recolor(r, c) for r in remains[i] if c != r]) 
    answer = min(answer, _answer)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

D = []
for i in range(C):
    D.append(list(map(int, input().split())))

remains = {0: [], 1: [], 2: []}

for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3].append(line[j])

INF = 65535

def recolor(x, y):
    return D[x-1][y-1]

memo = {0: {}, 1: {}, 2: {}}

answer = INF
for choice in permutations(list(range(1, C+1)), 3):
    _answer = 0
    for i in range(3):
        total = memo[i].get(
            choice[i],
            sum([recolor(r, choice[i]) for r in remains[i] if choice[i] != r])
        ) 
        memo[i][choice[i]] = total
        _answer += total 
    answer = min(answer, _answer)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

D = []
for i in range(C):
    D.append(list(map(int, input().split())))

remains = {0: [], 1: [], 2: []}

for i in range(1, N+1):
    line = list(map(int, input().split()))
    for j in range(N):
        remains[(i+j+1)%3].append(line[j])

INF = 65535

def recolor(x, y):
    return D[x-1][y-1]

answer = INF
for choice in permutations(list(range(1, C+1)), 3):
    _answer = 0
    for i in range(3):
        _answer += sum([recolor(r, choice[i]) for r in remains[i] if choice[i] != r])
    answer = min(answer, _answer)

print(answer)

Submission status: Time Limit Exceeded

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

D = []
c = []

for i in range(C):
    D.append(list(map(int,input().split())))
for i in range(N):
    c.append(list(map(int,input().split()))) 

c1 = []
c2 = []
c3 = []

from itertools import product

for i,j in product(range(N),repeat=2):
    if (i+j)%3 == 0:
        c1.append(c[i][j])
    elif (i+j)%3 == 1:
        c2.append(c[i][j])
    else:
        c3.append(c[i][j])
val=[]

for i in product(range(C),repeat=3):
    dif = 0
    if i[0]!=i[1] and i[1]!=i[2] and i[2]!=i[0]:
        for j in range(C):
            dif += D[j][i[0]] * c1.count(j+1)
            dif += D[j][i[1]] * c2.count(j+1)
            dif += D[j][i[2]] * c3.count(j+1)
        val.append(dif)

print(min(val))

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
d = []
c = []
for i in range(C):
    d.append(list(map(int, input().split())))
for i in range(N):
    c.append(list(map(int, input().split())))

s = [[0 for j in range(C)] for i in range(C)]

for l in range(C):
    for i in range(N):
        for j in range(N):
            s[(i + j) % 3][l] += d[c[i][j]-1][l]
                

m = 1000 * 500 * 500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and i != k and j != k:
                m = min(m, s[0][i] + s[1][j] + s[2][k])

print(m)

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
d = []
c = []
for i in range(C):
    d.append(list(map(int, input().split())))
for i in range(N):
    c.append(list(map(int, input().split())))

s = [[0 for j in range(C)] for i in range(C)]
for k in range(C):
    for l in range(C):
        for i in range(N):
            for j in range(N):
                if (i + j) % 3 == k:
                    s[k][l] += d[c[i][j]-1][l]
m = 1000 * 500 * 500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i != j and i != k and j != k:
                m = min(m, s[0][i] + s[1][j] + s[2][k])

print(m)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product, permutations
n, c = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(c)]
grid = [list(map(int, input().split())) for _ in range(n)]
cost = [[0] * c for _ in range(3)]

for i, j, k in product(range(n), range(n), range(c)):
    # cost[0][k] -> 余りが0になる場所の色をkに変えるときのコスト
    cost[(i + j + 2) % 3][k] += d[grid[i][j] - 1][k]

ans = []
for s, t, u in permutations(range(c), r=3):
    ans.append(cost[0][s] + cost[1][t] + cost[2][u])
print(min(ans))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations
N, C = map(int, input().split())
D = [int(_) for c in range(C) for _ in input().split()]
G = [int(_) for n in range(N) for _ in input().split()]

table = [0] * C * 3
for row in range(N):
    for col in range(N):
        i = (row + col) % 3
        for c in range(C):
            table[i * C + c] += D[C * (G[N * row + col] - 1) + c]


def cost(comb):
    return table[C * 0 + comb[0]] + table[C * 1 + comb[1]] + table[C * 2
                                                                   + comb[2]]


combs = permutations(range(C), 3)
min_cst = cost(min(combs, key=lambda comb: cost(comb)))
print(min_cst)

Submission status: Time Limit Exceeded

Solution code:
n,c=map(int,input().split())
d=[]
for _ in range(c):
	d.append([int(i) for i in input().split()])
e=[]
for _ in range(n):
	e.append([int(i) for i in input().split()])

i0=[]
i1=[]
i2=[]
for k in range(c):
	re=[0,0,0]
	for i in range(n):
		for j in range(n):
			re[(i+j)%3]+=d[e[i][j]-1][k]
	i0.append([k,re[0]])
	i1.append([k,re[1]])
	i2.append([k,re[2]])

i0.sort(key=lambda x:x[1])
i1.sort(key=lambda x:x[1])
i2.sort(key=lambda x:x[1])

ans=float('inf')
for i in range(3):
	for j in range(3):
		if i0[i][0]!=i1[j][0]:
			for k in range(3):
				if i0[i][0]!=i2[k][0] and i1[j][0]!=i2[k][0]:
					l=i0[i][1]+i1[j][1]+i2[k][1]
					if ans>l:
						ans=l
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

n, c = map(int, input().split())
color = [list(map(int, input().split()))for i in range(c)]  # 違和感
grid = [list(map(int, input().split()))for i in range(n)]  # 色
ans = 1000000000
cnt = 0
li = []
for i in range(c):
    li.append(i+1)
for mark in list(itertools.permutations(li, 3)):
    x = mark[0]  # 余り0をｘ、1をｙ、2をｚとする方法
    y = mark[1]
    z = mark[2]
    for i in range(n):
        for j in range(n):
            if (i+j) % 3 == 0:
                cnt += color[grid[i][j]-1][x-1]
            elif (i+j) % 3 == 1:
                cnt += color[grid[i][j]-1][y-1]
            elif (i+j) % 3 == 2:
                cnt += color[grid[i][j]-1][z-1]
    if cnt < ans:
        ans = cnt
    cnt = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
D = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i) for i in input().split()] for _ in range(N)]

top3 = [[[0,1000*500*500] for _ in range(5)] for _ in range(3)]

for i in range(C):
        dif = [0]*3
        for j in range(N):
                for k in range(N):
                        dif[(j+k)%3] += D[c[j][k]-1][i]

        for l in range(3):
                for m in range(3):
                        if top3[l][m][1] > dif[l]:
                                top3[l][m+2][0] = top3[l][m+1][0]
                                top3[l][m+2][1] = top3[l][m+1][1]
                                top3[l][m+1][0] = top3[l][m][0]
                                top3[l][m+1][1] = top3[l][m][1]
                                top3[l][m][0] = i
                                top3[l][m][1] = dif[l]
                                break


ans = 1000*500*500
for i in range(3):
        for j in range(3):
                for k in range(3):
                        if top3[0][i][0] != top3[1][j][0] and top3[0][i][0] != top3[2][k][0] and top3[1][j][0] != top3[2][k][0]:
                                if ans > top3[0][i][1] + top3[1][j][1] + top3[2][k][1]:
                                        ans = top3[0][i][1] + top3[1][j][1] + top3[2][k][1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import functools

def inp():
  return list(map(int, input().split()))

N,C = inp()
D = [[0] * (C+1)]
c = [[], [], []]
for i in range(C):
  D.append([0] + inp())
for i in range(N):
  l = inp()
  for j in range(N):
    c[(i+j)%3].append(l[j])

# print(N,C,D,c)

sc = list(itertools.permutations(list(range(1,C+1)), 3))
# print(sc)

ret = []
for sc_i in sc:
  ret.append(0)
  for i in range(3):    
    ret[-1] += (sum(list(map(lambda x: D[x][sc_i[i]], c[i]))))
  #print(ret[-1])

print(min(ret))

Submission status: Time Limit Exceeded

Solution code:
ans=10**9
N,C=map(int,input().split())
s=[list(map(int,input().split())) for i in range(C)]
t=[list(map(int,input().split())) for i in range(N)]
u=[[0]*C for i in range(3)]
for i in range(N):
    for j in range(N):
        for k in range(C):
            u[(i+j)%3][k]+=s[t[i][j]-1][k]
from itertools import permutations
for i,j,k in list(permutations(range(C),3)):
    p=u[0][i]+u[1][j]+u[2][k]
    ans=min(ans,p)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
ans=10**9
N,C=map(int,input().split())
s=[list(map(int,input().split())) for i in range(C)]
t=[list(map(int,input().split())) for i in range(N)]
u=[np.zeros((C)) for i in range(3)]
for i in range(N):
    for j in range(N):
        pass
        u[(i+j)%3]+=np.array(s[t[i][j]-1])
from itertools import permutations
for i,j,k in list(permutations(range(C),3)):
    p=u[0][i]+u[1][j]+u[2][k]
    ans=min(ans,p)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
N,C=map(int,input().split(' '))
D=[]
for _ in range(C):
  D.append([ x for x in map(int,input().split(' '))])

c=[]
for _ in range(N):
  c.append([ x for x in map(int,input().split(' '))])

x=float('inf')

for seq in [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]]:
  counter=[[0]*C for _ in range(3)]
  for i in range(N):
    for j in range(N):
      b=i%3
      cur=c[i][j]
      counter[seq[(j+b)%3]][cur-1]+=1
      #s+=D[cur-1][seq[(j+b)%3]]
  for c0 in range(C):
    for c1 in range(C):
      if c1==c0:
        continue
      for c2 in range(C):
        if c2==c0 or c2==c1:
          continue
        s=0
        for i, cx in enumerate(counter[0]):
          s+=D[i][c0]*cx
        for i, cx in enumerate(counter[1]):
          s+=D[i][c1]*cx
        for i, cx in enumerate(counter[2]):
          s+=D[i][c2]*cx
        if s<x:
          x=s

print(x)

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
n=int(x[0])
c=int(x[1])
dlist=[0]*(c*c)
clist=[0]*(n*n)
cost1=[]
cost2=[]
cost3=[]
x=0
for j in range (c):
    a=input().split()
    for i in a:
        dlist[x]=int(i)
        x=x+1
x=0
for j in range (n):
    a=input().split()
    for i in a:
        clist[x]=int(i)
        x+=1
x=0
list1=[]
list2=[]
list3=[]
y=0
yy=0
while y<n:
    while yy<n:
        if (y+yy)%3==0:
            list1.append(clist[y*n+yy])
        elif (y+yy)%3==1:
            list2.append(clist[y*n+yy])
        elif (y+yy)%3==2:
            list3.append(clist[y*n+yy])
        yy=yy+1
    y=y+1
    yy=0
 
y=1
y2=1
y3=1
mini=99999999999999999999
while y<=c:
    cost=0
    for i in list1:
        if i!=y:
            cost=cost+dlist[(i-1)*c+y-1]
    cost1.append(cost)
    y=y+1
while y2<=c:
    cost=0
    for i in list2:
        if i!=y2:
            cost=cost+dlist[(i-1)*c+y2-1]
    cost2.append(cost)
    y2=y2+1
while y3<=c:
    cost=0
    for i in list3:
        if i!=y3:
            cost=cost+dlist[(i-1)*c+y3-1]
    cost3.append(cost)
    y3=y3+1
x=1
x2=2
x3=3
while x<=c:
    while x2<=c:
        if x2==x:
            x2+=1
        if x2>c:
            break
        while x3<=c:
            if x3==x or x3==x2:
                x3+=1
            if x3==x or x3==x2:
                x3+=1
            if x3>c:
                break
            
            mini=min(mini, cost1[x-1]+cost2[x2-1]+cost3[x3-1])
            x3+=1
        x2+=1
        x3=1
    x+=1
    x2=1
    x3=1
 
print(mini)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, C = map(int, input().split())
D = []
for _ in range(C):
    D.append(list(map(int, input().split())))
c = []
for _ in range(N):
    c.append(list(map(lambda x: int(x) - 1, input().split())))


min_diff = float("inf")
for ccs in itertools.permutations(range(C), 3):
    diff = 0
    for i in range(N):
        for j in range(N):
            diff += D[c[i][j]][ccs[(i + j) % 3]]
    min_diff = min(min_diff, diff)

print(min_diff)

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
n=int(x[0])
c=int(x[1])
dlist=[]
clist=[]
cost1=[]
cost2=[]
cost3=[]
for i in range (c):
    a=input().split()
    for i in a:
        dlist.append(int(i))
for i in range (n):
    a=input().split()
    for i in a:
        clist.append(int(i))
list1=[]
list2=[]
list3=[]
y=0
yy=0
while y<n:
    while yy<n:
        if (y+yy)%3==0:
            list1.append(clist[y*n+yy])
        elif (y+yy)%3==1:
            list2.append(clist[y*n+yy])
        elif (y+yy)%3==2:
            list3.append(clist[y*n+yy])
        yy=yy+1
    y=y+1
    yy=0

y=1
y2=1
y3=1
mini=99999999999999999999
while y<=c:
    cost=0
    for i in list1:
        if i!=y:
            cost=cost+dlist[(i-1)*c+y-1]
    cost1.append(cost)
    y=y+1
while y2<=c:
    cost=0
    for i in list2:
        if i!=y2:
            cost=cost+dlist[(i-1)*c+y2-1]
    cost2.append(cost)
    y2=y2+1
while y3<=c:
    cost=0
    for i in list3:
        if i!=y3:
            cost=cost+dlist[(i-1)*c+y3-1]
    cost3.append(cost)
    y3=y3+1
x=1
x2=2
x3=3
while x<=c:
    while x2<=c:
        if x2==x:
            x2+=1
        if x2>c:
            break
        while x3<=c:
            if x3==x or x3==x2:
                x3+=1
            if x3==x or x3==x2:
                x3+=1
            if x3>c:
                break
            
            mini=min(mini, cost1[x-1]+cost2[x2-1]+cost3[x3-1])
            x3+=1
        x2+=1
        x3=1
    x+=1
    x2=1
    x3=1

print(mini)

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())              # 同上。map関数を使うとこのように書ける

D = [[0 for i in range(C)] for j in range(C)]
c = [[0 for i in range(N)] for j in range(N)]
# iwakan = [[[0 for i in range(N)] for j in range(N)] for k in range(C)]

for i in range(C):
    D[i] = list(map(int, input().split()))

for i in range(N):
    c[i] = list(map(int, input().split()))

# まず違和感リストを作る。
# for i in range(C):
#     for j in range(N):
#         for k in range(N):
#             iwakan[i][j][k] = D[c[j][k] - 1][i]

'''
Gij0 : (i + j) % 3 == 0 となる場所
Gij1 : (i + j) % 3 == 1 となる場所
Gij2 : (i + j) % 3 == 2 となる場所
とした時に、
Gijnに属する場所全ての色をaに塗り替える場合の違和感の合計を
iwakan[n][a]とする。
iwakan[n][a]を全て求めるための計算量は、30*500*500 = 7500000
iwakan を用いて全ての色の塗り替えの組み合わせを求めるための計算量は
30 * 29 * 28 = 24360
'''

iwakan = [[0 for i in range(C)] for j in range(3)]

for a in range(C):
    for i in range(N):
        for j in range(N):
            if (i + j) % 3 == 0:
                iwakan[0][a] = iwakan[0][a] + D[c[i][j] - 1][a]
            elif (i + j) % 3 == 1:
                iwakan[1][a] = iwakan[1][a] + D[c[i][j] - 1][a]
            else:
                iwakan[2][a] = iwakan[2][a] + D[c[i][j] - 1][a]

sum_min = float("inf")
for i in range(C):
    for j in range(C):
        for k in range(C):
            if (i == j) or (j == k) or (k == i):
                pass
            else:
                sum_tmp = iwakan[0][i] + iwakan[1][j] + iwakan[2][k]
                if sum_min > sum_tmp:
                    sum_min = sum_tmp

print(sum_min)

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())              # 同上。map関数を使うとこのように書ける

D = [[0 for i in range(C)] for j in range(C)]
c = [[0 for i in range(N)] for j in range(N)]
# iwakan = [[[0 for i in range(N)] for j in range(N)] for k in range(C)]

for i in range(C):
    D[i] = list(map(int, input().split()))

for i in range(N):
    c[i] = list(map(int, input().split()))

# まず違和感リストを作る。
# for i in range(C):
#     for j in range(N):
#         for k in range(N):
#             iwakan[i][j][k] = D[c[j][k] - 1][i]

# 違和感リストから違和感の合計直を求める。
sum_min = float("inf")

for i in range(C):
    for j in range(C):
        for k in range(C):
            if (i == j) or (j == k) or (k == i):
                pass
            else:
                sum_tmp = 0
                for l in range(N):
                    for m in range(N):
                        if(l + m) % 3 == 0:
                            # sum_tmp = sum_tmp + iwakan[i][l][m]
                            sum_tmp = sum_tmp + D[c[l][m] - 1][i]
                        elif(l + m) % 3 == 1:
                            # sum_tmp = sum_tmp + iwakan[j][l][m]
                            sum_tmp = sum_tmp + D[c[l][m] - 1][j]
                        else:
                            # sum_tmp = sum_tmp + iwakan[k][l][m]
                            sum_tmp = sum_tmp + D[c[l][m] - 1][k]
                if sum_min > sum_tmp:
                    sum_min = sum_tmp

print(sum_min)

Submission status: Time Limit Exceeded

Solution code:
N, C = tuple(map(int, input().split()))
D = [[int(x) for x in input().split()] for i in range(0, C)]
c = [[int(x) - 1 for x in input().split()] for i in range(0, N)]

# E[p][q]: (i+j)%3==p となるセルすべてを色qに変えた時の違和感の総和
E = [[0 for i in range(C)] for j in range(3)]
for i in range(0, N):
    for j in range(0, N):
        for q in range(0, C):
            E[(i + j) % 3][q] += D[c[i][j]][q]

m1 = sorted(E[0])[2]
m2 = sorted(E[1])[2]
m3 = sorted(E[2])[2]

m = 1000 * (N ** 2)
for i in range(C):
    if E[0][i] > m1:
        continue
    n1 = E[0][i]
    for j in range(C):
        if j == i:
            continue
        if E[1][j] > m2:
            continue
        n2 = n1 + E[1][j]
        if n2 > m:
            continue
        for k in range(C):
            if k == i or k == j:
                continue
            if E[2][k] > m3:
                continue
            n3 = n2 + E[2][k]
            if n3 < m:
                m = n3
print(m)

Submission status: Time Limit Exceeded

Solution code:
N, C = tuple(map(int, input().split()))
D = [[int(x) for x in input().split()] for i in range(0, C)]
c = [[int(x) - 1 for x in input().split()] for i in range(0, N)]

# E[p][q]: (i+j)%3==p となるセルすべてを色qに変えた時の違和感の総和
E = [[0 for i in range(C)] for j in range(3)]
for p in range(0, 3):
    for i in range(0, N):
        for j in range(0, N):
            if (i + j) % 3 == p:
                for q in range(0, C):
                    E[p][q] += D[c[i][j]][q]

m1 = sorted(E[0])[2]
m2 = sorted(E[1])[2]
m3 = sorted(E[2])[2]

m = 1000 * (N ** 2)
for i in range(C):
    if E[0][i] > m1:
        continue
    n1 = E[0][i]
    for j in range(C):
        if j == i:
            continue
        if E[1][j] > m2:
            continue
        n2 = n1 + E[1][j]
        if n2 > m:
            continue
        for k in range(C):
            if k == i or k == j:
                continue
            if E[2][k] > m3:
                continue
            n3 = n2 + E[2][k]
            if n3 < m:
                m = n3
print(m)

Submission status: Time Limit Exceeded

Solution code:
N, C = tuple(map(int, input().split()))
D = [[int(x) for x in input().split()] for i in range(0, C)]
c = [[int(x) - 1 for x in input().split()] for i in range(0, N)]

# E[p][q]: (i+j)%3==p となるセルすべてを色qに変えた時の違和感の総和
E = [[0 for i in range(C)] for j in range(3)]
for p in range(0, 3):
    for i in range(0, N):
        for j in range(0, N):
            if (i + j) % 3 == p:
                for q in range(0, C):
                    E[p][q] += D[c[i][j]][q]

m = 1000 * (N ** 2)
for i in range(C):
    n1 = E[0][i]
    if n1 > m:
        continue
    for j in range(C):
        if j == i:
            continue
        n2 = n1 + E[1][j]
        if n2 > m:
            continue
        for k in range(C):
            if k == i or k == j:
                continue
            n3 = n2 + E[2][k]
            if n3 < m:
                m = n3
print(m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
# from itertools import permutations

i = sys.stdin
N, C = map(int, i.readline().strip().split())
D = [[int(_) for _ in i.readline().strip().split()] for c in range(C)]
G = [[int(_) for _ in i.readline().strip().split()] for c in range(N)]

table = [[0 for c in range(C)] for _ in range(3)]
for row in range(N):
    for col in range(N):
        i = (row + col) % 3
        for c in range(C):
            table[i][c] += D[G[row][col] - 1][c]

cst = 1000 * 500**2
for c0 in range(C):
    for c1 in range(C):
        if c0 == c1:
            continue
        for c2 in range(C):
            if c1 == c2 or c2 == c0:
                continue
            cst = min(cst, table[0][c0] + table[1][c1] + table[2][c2])

# combs = permutations(range(C), 3)
# for comb in combs:
#     cst = min(cst, table[0][comb[0]] + table[1][comb[1]] + table[2][comb[2]])

print(cst)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import permutations

i = sys.stdin
N, C = map(int, i.readline().strip().split())
D, G = [], []
for c in range(C):
    D += [int(_) for _ in i.readline().strip().split()]
for n in range(N):
    G += [int(_) for _ in i.readline().strip().split()]

table0 = [0 for c in range(C)]
table1 = [0 for c in range(C)]
table2 = [0 for c in range(C)]
for row in range(N):
    for col in range(N):
        i = (row + col) % 3
        for c in range(C):
            if i == 0:
                table0[c] += D[(G[row * N + col] - 1) * C + c]
            elif i == 1:
                table1[c] += D[(G[row * N + col] - 1) * C + c]
            else:
                table2[c] += D[(G[row * N + col] - 1) * C + c]

cst = 1000 * 500**2
combs = permutations(range(C), 3)
for comb in combs:
    cst = min(cst, table0[comb[0]] + table1[comb[1]] + table2[comb[2]])

print(cst)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import permutations

i = sys.stdin
N, C = map(int, i.readline().strip().split())
D = [[int(_) for _ in i.readline().strip().split()] for c in range(C)]
G = [[int(_) for _ in i.readline().strip().split()] for n in range(N)]

table0 = [0 for c in range(C)]
table1 = [0 for c in range(C)]
table2 = [0 for c in range(C)]
for row in range(N):
    for col in range(N):
        i = (row + col) % 3
        for c in range(C):
            if i == 0:
                table0[c] += D[G[row][col] - 1][c]
            elif i == 1:
                table1[c] += D[G[row][col] - 1][c]
            else:
                table2[c] += D[G[row][col] - 1][c]

cst = 1000 * 500**2
combs = permutations(range(C), 3)
for comb in combs:
    cst = min(cst, table0[comb[0]] + table1[comb[1]] + table2[comb[2]])

print(cst)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from itertools import permutations

i = sys.stdin
N, C = map(int, i.readline().strip().split())
D = [[int(_) for _ in i.readline().strip().split()] for c in range(C)]
G = [[int(_) for _ in i.readline().strip().split()] for n in range(N)]

table = [[0 for c in range(C)] for _ in range(3)]
for c in range(C):
    for row in range(N):
        for col in range(N):
            table[(row + col) % 3][c] += D[G[row][col] - 1][c]

cst = 1000 * 500**2
combs = permutations(range(C), 3)
for comb in combs:
    cst = min(cst, table[0][comb[0]] + table[1][comb[1]] + table[2][comb[2]])

print(cst)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from itertools import permutations
N, C = map(int, input().split())
D = [[int(_) for _ in input().split()] for i in range(C)]
G = [[int(_) for _ in input().split()] for i in range(N)]

table = [[0 for c in range(C)] for _ in range(3)]
for c in range(C):
    for row in range(N):
        for col in range(N):
            table[(row + col) % 3][c] += D[G[row][col] - 1][c]

cst = 1000 * 500**2
combs = permutations(range(C), 3)
for comb in combs:
    tmp = table[0][comb[0]] + table[1][comb[1]] + table[2][comb[2]]
    if tmp < cst:
        cst = tmp

print(cst)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, c = map(int, input().split())
    d = [list(map(int, input().split())) for i in range(c)]
    grid = [list(map(int, input().split())) for i in range(n)]

    group = [[0 for i in range(c)], [0 for i in range(c)], [0 for i in range(c)]]
    for i in range(n):
        for j in range(n):
            for color in range(c):
                group[(i+j) % 3][color] += d[grid[i][j]-1][color]

    min_cost = 1 << 30
    for i in range(c):
        for j in range(c):
            if i != j:
                for k in range(c):
                    if j != k and k != i:
                        min_cost = min(group[0][i]+group[1][j]+group[2][k], min_cost)

    print(min_cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
Dij =[]
cij =[]

for i in range(C):
    tmp = list(map(int, input().split()))
    Dij.append(tmp)
for i in range(N):
    tmp = list(map(int, input().split()))
    cij.append(tmp)



std =[]
for i in range(C):
    for j in range(C):
        if j == i: continue
        tmp2 =[]
        for k in range(C):
            if k == j or k == i: continue
            for l in range(N):
                tmp1 =[]
                for m in range(N):
                    if (l + 1 + m + 1) % 3 == 1:
                        tmp1.append(i+1)
                    elif (l + 1 + m + 1) % 3 == 2:
                        tmp1.append(j+1)
                    elif (l + 1 + m + 1) % 3 == 0:
                        tmp1.append(k+1)
                tmp2.append(tmp1)
            std.append(tmp2)

diff = []
for k in range(len(std)):
    difference = 0
    for i in range(N):
        for j in range(N):
            if cij[i][j] != std[k][i][j]:
                difference += Dij[cij[i][j]-1][std[k][i][j]-1]
    diff.append(difference)

print(min(diff))

Submission status: Time Limit Exceeded

Solution code:
n, c = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(c)]
C = [[int(i) for i in input().split()] for j in range(n)]

# for i in range(c):
#   for j in range(c):
#     for k in range(c):
#       d = D[i][j] + D[j][k]
#       if D[i][k] > d:
#         D[i][k] = d

sum_d = [[0] * c for i in range(3)]

for i in range(n):
  for j in range(n):
    for k in range(c):
      sum_d[(i+j)%3][k] += D[C[i][j]-1][k]
      
max_d = 1000 * (n//3+1)
ans = max_d * n**2
      
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i != j != k != i:
        ans = min(ans, sum_d[0][i] + sum_d[1][j] + sum_d[2][k])
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,C=[int(x) for x in str(input()).split()]
D=[[0 for x in range(0,C+1)]]
for i in range (0,C):
  D.append([0]+[int(x) for x in str(input()).split()])
c=[[0 for x in range(0,N+1)]]
for j in range(0,N):
  c.append([0]+[int(x) for x in str(input()).split()])


error=1000000000
for i in range(1,C+1):
  for j in range(1,C+1):
    if j!=i:
      for k in range(1,C+1):
        if k!=j:
          if k!=i:
            
            e=0
            for x in range(1,N+1):
              for y in range(1,N+1):
                
                if (x+y)%3==0:
                  e+=D[c[x][y]][i]
                elif (x+y)%3==1:
                  e+=D[c[x][y]][j]
                elif (x+y)%3==2:
                  e+=D[c[x][y]][k]
                if e>error:
                  break
       
            error=min(error,e)
print(error)

Submission status: Time Limit Exceeded

Solution code:
N,C=[int(x) for x in str(input()).split()]
D=[[0 for x in range(0,C+1)]]
for i in range (0,C):
  D.append([0]+[int(x) for x in str(input()).split()])
c=[[0 for x in range(0,N+1)]]
for j in range(0,N):
  c.append([0]+[int(x) for x in str(input()).split()])


error=1000000000
for i in range(1,C+1):
  for j in range(1,C+1):
    if j!=i:
      for k in range(1,C+1):
        if k!=j:
          if k!=i:
            
            e=0
            for x in range(1,N+1):
              for y in range(1,N+1):
                
                if (x+y)%3==0:
                
                  e+=D[c[x][y]][i]
                elif (x+y)%3==1:
              
                  e+=D[c[x][y]][j]
                elif (x+y)%3==2:
              
                  e+=D[c[x][y]][k]
                
       
            error=min(error,e)
print(error)