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 = [int(i) for i in input().split(" ")]
d = [0 for i in range(0, c + 1)]
a = [0 for i in range(0, n + 1)]

for i in range(1, c + 1):
    d[i] = [0] + [int(i) for i in input().split(" ")]

for i in range(1, n + 1):
    a[i] = [0] + [int(i) for i in input().split(" ")]
    
m = [[] for i in range(0, 3)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        m[(i + j) % 3].append(a[i][j])

d_min = 1000*500*500

def s(p):
    ca = [True] * (c + 1)
    c_min = 0
    global d_min
    d_min_t_sum = 0
    for mod in p:
        d_min_t = 1000*500*500
        for ci in range(1, c + 1):
            if ca[ci]:
                d_sum = sum([d[mi][ci] for mi in m[mod]])
                #print(d_sum)
                if d_sum < d_min_t:
                    d_min_t = d_sum
                    c_min = ci
        ca[c_min] = False
        d_min_t_sum += d_min_t
    if d_min_t_sum < d_min:
        d_min = d_min_t_sum
        
s([0, 1, 2])
s([0, 2, 1])
s([1, 0, 2])
s([1, 2, 0])
s([2, 1, 0])
s([2, 0, 1])

print(d_min)

Submission status: Time Limit Exceeded

Solution code:
n, c = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(c)]
grid = [list(map(int, input().split())) for _ in range(n)]

lst_0 = []
lst_1 = []
lst_2 = []
for i in range(n):
    for j in range(n):
        if (i+j+2) % 3 == 0:
            lst_0.append(grid[i][j])
        elif (i+j+2) % 3 == 1:
            lst_1.append(grid[i][j])
        else:
            lst_2.append(grid[i][j])

cost0 = []
for i in range(1, c+1):
    C = 0
    for j in lst_0:
        if j != i:
            C += cost[j-1][i-1]
    cost0.append(C)

cost1 = []
for i in range(1, c+1):
    C = 0
    for j in lst_1:
        if j != i:
            C += cost[j-1][i-1]
    cost1.append(C)

cost2 = []
for i in range(1, c+1):
    C = 0
    for j in lst_2:
        if j != i:
            C += cost[j-1][i-1]
    cost2.append(C)

min_cost = 10**100
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i != j and j != k and k != i:
                min_cost = min(min_cost, cost0[i]+cost1[j]+cost2[k])
print(min_cost)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

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

# (i + j) % 3 = k のマスを色cに塗り替える際の違和感の和
dp = {
    k: [
        sum(
            D[c[i][j] - 1][k - 1] if (i + j) % 3 == m else
            0
            for i in range(N)
            for j in range(N)
        )
        for m in range(3)
    ]
    for k in range(1, C + 1)
}

# dpを用いて全探索し解を得る
ans = min(
    dp[i][0] + dp[j][1] + dp[k][2]
    for i, j, k in permutations(range(1, C + 1), 3)
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                #print(i,ans[k], a)
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])

    return

#D
def D():
    n, c = LI()
    D = LIR(c)
    C = LIR_(n)
    CL = list(itertools.permutations(range(c), 3))
    ans = inf
    for c0, c1, c2 in CL:
        ansb = 0
        for y in range(n):
            for x in range(n):
                amari = (x + y) % 3
                if amari == 0:
                    ansb += D[C[y][x]][c0]
                if amari == 1:
                    ansb += D[C[y][x]][c1]
                if amari == 2:
                    ansb += D[C[y][x]][c2]
        ans = min(ans, ansb)
    print(ans)

    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
c_set = set([])
for c_ in c:
    c_set |= set(c_)
ans = 1e9
for c_1 in range(C):
    for c_2 in range(C):
        for c_3 in range(C):
            if not (c_1 in c_set or c_2 in c_set or c_3 in c_set):
                continue
            if c_1==c_2 or c_1==c_3 or c_2==c_3:
                continue
            c_list = [c_1,c_2,c_3]
            k = 0
            for i in range(N):
                for j in range(N):
                    if not c[i][j]==c_list[(i+j)%3]:
                        k += d[c[i][j]-1][c_list[(i+j)%3]-1]
            ans = min(ans,k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
d = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
ans = 1e9
for c_1 in range(C):
    for c_2 in range(C):
        for c_3 in range(C):
            if c_1==c_2 or c_1==c_3 or c_2==c_3:
                continue
            c_list = [c_1,c_2,c_3]
            k = 0
            for i in range(N):
                for j in range(N):
                    if not c[i][j]==c_list[(i+j)%3]:
                        k += d[c[i][j]-1][c_list[(i+j)%3]-1]
            ans = min(ans,k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools


def get_discomfort(group, color, D):
    s = 0
    for c in group:
        s += D[c - 1][color - 1]
    return s


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


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

ans = float("inf")
for colors in itertools.permutations(list(range(C)), 3):
    colors = list(colors)
    s = 0
    for i, c in enumerate(colors):
        s += get_discomfort(grids[i], c, D)
    ans = min(ans, s)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, C = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

r0 = []
r1 = []
r2 = []
for i in range(N):
    for j in range(N):
        rest = (i+1+j+1) % 3
        if rest == 0:
            r0.append(c[i][j]-1)
        elif rest == 1:
            r1.append(c[i][j]-1)
        else:
            r2.append(c[i][j]-1)
ans = 10**10
for p in permutations([i for i in range(C)], 3):
    point = 0
    point += sum([d[rest][p[0]] for rest in r0])
    point += sum([d[rest][p[1]] for rest in r1])
    point += sum([d[rest][p[2]] for rest in r2])
    ans = min(ans, point)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
n,c=map(int,input().split())
d=[list(map(int,input().split()))for i in range(c)]
s=[i for i in range(c)]
p=list(itertools.permutations(s))
h=[list(map(int,input().split()))for i in range(n)]
a=[[]for i in range(3)]
for i in range(n):
    for j in range(n):
        a[(i+j+2)%3].append(h[i][j])
c=float("inf")
for x in range(len(p)):
    g=0
    for i in range(3):
        for j in range(len(a[i])):
            g+=d[a[i][j]-1][p[x][i]]
    c=min(c,g)
print(c)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, C = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(C)]
v = [[int(i) - 1 for i in input().split()] for j in range(N)]

table = list(permutations(range(C), 3))
ans = float('inf')

for a, b, c in table:
    dep = 0
    for i in range(N):
        for j in range(N):
            num = v[i][j]
            if (i+j)%3 == 0:
                dep += D[num][a]
            elif (i+j)%3 == 1:
                dep += D[num][b]
            else:
                dep += D[num][c]
    if ans > dep:
        ans = dep
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations

N, C = [int(i) for i in input().split()]
D = [[int(i) for i in input().split()] for j in range(C)]
v = [[int(i) - 1 for i in input().split()] for j in range(N)]

table = list(permutations(range(C), 3))
ans = []

for a, b, c in table:
    dep = 0
    for i in range(N):
        for j in range(N):
            num = v[i][j]
            if (i+j)%3 == 0:
                dep += D[num][a]
            elif (i+j)%3 == 1:
                dep += D[num][b]
            else:
                dep += D[num][c]
    ans.append(dep)
print(min(ans))

Submission status: Time Limit Exceeded

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

def main():
    na = list(map(int, input().split()))
    N, C = na[0], na[1]

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

    s = []
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))
    s.append([0] * (C + 1))

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

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


    print(s_min)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
n, x = map(int, input().split())
d = [tuple(map(int, input().split())) for _ in range(x)]
c = [tuple(map(int, input().split())) for _ in range(n)]

ans = float("inf")
for v in itertools.permutations(list(range(1, x+1)), 3):
    tmp2 = 0
    for i in range(3):
        tmp1 = 0
        j = 0
        k = i
        while k <= 2*n-2:
            for l in range(n):
                if -l + k < 0 or -l + k >= n:
                    continue
                tmp1 += d[c[-l+k][l]-1][v[i]-1]
            j += 1
            k = 3*j+i
        tmp2 += tmp1
    ans = min(ans, tmp2)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]


for i in range(N):
    for j in range(N):
        pattern = (i + j) % 3
        for toC in range(C):
            I[toC][pattern] += D[c[i][j] - 1][toC]


ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]

for color in range(C):
    for i in range(N):
        for j in range(N):
            pattern = (i + j) % 3
            I[color][pattern] += D[c[i][j] - 1][color]

ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]

for color in range(C):
    for i in range(N):
        for j in range(N):
            pattern = (i + j) % 3
            I[color][pattern] += D[c[i][j] - 1][color]

ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        for p3 in range(C):
            if p1 == p3 or p2 == p3 or p1 == p2:
                continue
            ans = min(ans, I[p1][0] + I[p2][1] + I[p3][2])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]  # 違和感
G = [list(map(int, input().split())) for i in range(N)]  # 初期盤面
X = [[0] * C for i in range(3)]  # modが0~2 × 各色への変更 の違和感の和

for c in range(C):  # 色
    tmp = [0] * 3  # 各modの違和感の和
    for i in range(N):
        for j in range(N):
            tmp[(i + j) % 3] += D[G[i][j] - 1][c]
    for t in range(3):
        X[t][c] = tmp[t]

ans = float('inf')
for c1, c2, c3 in permutations(range(C), 3):
    ans = min(ans, X[0][c1] + X[1][c2] + X[2][c3])

print(ans)

Submission status: Time Limit Exceeded

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

"""
参考：http://drken1215.hatenablog.com/entry/2018/07/22/133200
　　　https://www.hamayanhamayan.com/entry/2018/06/16/091039
・自力ACできたけど、メモをもう一歩深く書けば
　メインのループ1つ落とせるのが分かったのでそっちもやってみる。
"""
 
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
cN = [list(map(int, input().split())) for i in range(N)]

# [mod 3でどれになるか][今度の色] = そうなった時の違和感の総和
memo = [[0] * C for i in range(3)]
for c in range(C):
    for i in range(N):
        for j in range(N):
            memo[(i+j+2)%3][c] += D[cN[i][j]-1][c]

ans = 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:
                continue
            # メモで違和感の合計まで出してあるので、ここではループなし
            sm = memo[0][i] + memo[1][j] + memo[2][k]
            ans = min(sm, ans)
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)]
modl = [[] for i in range(3)]
for i in range(N):
    for j in range(N):
        modl[((i+1)+(j+1))%3].append(c[i][j])
ans = float('inf')
for i in range(C):
    total = 0
    tmp1 = 0
    for e in modl[0]:
        tmp1 += D[e-1][i]
    total += tmp1
    for j in range(C):
        if i!=j:
            tmp2 = 0
            for e in modl[1]:
                tmp2 += D[e-1][j]
            total += tmp2
            for k in range(C):
                tmp3 = 0
                if i!=k and j!=k:
                    for e in modl[2]:
                        tmp3 += D[e-1][k]
                    total += tmp3
                    ans = min(ans,total)
                    total -= tmp3
            total -= tmp2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, raw_input().split())
 
D = [ [int(i) for i in raw_input().split()] for _ in xrange(C) ]
c = [ [int(i) for i in raw_input().split()] for _ in xrange(N) ]
 
costD = [ [0, 0, 0] for _ in xrange(C)]
 
for c0 in xrange(C):
    for i in xrange(N):
        for j in xrange(N):
            costD[c0][(i+j)%3] += D[c[i][j]-1][c0]
 
kohoD = []
 
for c1 in xrange(C):
    for c2 in xrange(C):
        if c1 == c2:
            continue
        for c3 in xrange(C):
            if c1 == c3 or c2 == c3:
                continue
            kohoD += [(costD[c1][0] + costD[c2][1] + costD[c3][2])]
 
print(min(kohoD))

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) ]

costD = [ [0, 0, 0] for _ in range(C)]

for c0 in range(C):
    for i in range(N):
        for j in range(N):
            costD[c0][(i+j)%3] += D[c[i][j]-1][c0]

kohoD = []

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            kohoD += [(costD[c1][0] + costD[c2][1] + costD[c3][2])]

print(min(kohoD))

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) ] 

costD = [0 for _ in range(C)]

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

kohoD = []

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            kohoD += [(costD[c1][0] + costD[c2][1] + costD[c3][2])]

print(min(kohoD))

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) ] 

costD = [0 for _ in range(C)]

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

kohoD = []

for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            kohoD += [(costD[c1][0] + costD[c2][1] + costD[c3][2])]

print(sorted(kohoD)[0])

Submission status: Time Limit Exceeded

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

for _ in range(N):
    c.append([int(i) for i in input().split()])

costD = []
for c0 in range(C):
    tmpD = [0] * 3
    for i in range(N):
        for j in range(N):
            tmpD[(i+j)%3] += D[c[i][j]-1][c0]
    costD.append(tmpD)

kohoD = []
for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            kohoD.append(costD[c1][0] + costD[c2][1] + costD[c3][2])

kohoD.sort()
print(kohoD[0])

Submission status: Time Limit Exceeded

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

for _ in range(N):
    c.append([int(i) for i in input().split()])


ansD = []
for c1 in range(C):
    for c2 in range(C):
        if c1 == c2:
            continue
        for c3 in range(C):
            if c1 == c3 or c2 == c3:
                continue
            sumD = 0
            for i in range(N):
                for j in range(N):
                    if (i+j) % 3 == 0:
                        goodc = c1
                    if (i+j) % 3 == 1:
                        goodc = c2
                    if (i+j) % 3 == 2:
                        goodc = c3
                    sumD += D[c[i][j]-1][goodc]
            ansD.append(sumD)
ansD.sort()
print(ansD[0])

Submission status: Time Limit Exceeded

Solution code:
N, C = map(int, input().split())
D = [[int(i) for i in input().split()] for c in range(C)]
Ini = [[int(i) for i in input().split()] for n in range(N)]
Mod0, Mod1, Mod2 = [[0, c] for c in range(C)], [[0, c] for c in range(C)], [[0, c] for c in range(C)]

for i in range(N):
    for j in range(N):
        k = i+j+2
        if k%3==0:
            for c in range(C):
                Mod0[c][0] += D[Ini[i][j]-1][c]
        elif k%3==1:
            for c in range(C):
                Mod1[c][0] += D[Ini[i][j]-1][c]
        else:
            for c in range(C):
                Mod2[c][0] += D[Ini[i][j]-1][c]
Mod0.sort()
Mod1.sort()
Mod2.sort()
Ans = float("inf")
for a in range(3):
    A = Mod0[a]
    for b in range(3):
        B = Mod1[b]
        for c in range(3):
            C = Mod2[c]
            if A[1] != B[1] and B[1] != C[1] and C[1] != A[1]:
                Ans = min(Ans, A[0]+B[0]+C[0])
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
def run(N, C, D, c):
    '''
    マス番号に応じて3色に塗る必要がある
    (i+j)%3が0, 1, 2それぞれに対して、ある色に塗るコストを計算する
    0, 1, 2それぞれのC色のコストのパターンができる
    上記コストに対してC色から3色を選択する全パターンのうち最小のコストを求める
    '''
    cost0 = {}
    cost1 = {}
    cost2 = {}
    for k in range(C):
        cost0[k] = 0
        cost1[k] = 0
        cost2[k] = 0
        for i in range(N):
            for j in range(N):
                if (i+j+2) % 3 == 0:
                    color = c[i][j] - 1
                    cost = D[color][k]
                    cost0[k] += cost
                elif (i+j+2) % 3 == 1:
                    color = c[i][j] - 1
                    cost = D[color][k]
                    cost1[k] += cost
                elif (i+j+2) % 3 == 2:
                    color = c[i][j] - 1
                    cost = D[color][k]
                    cost2[k] += cost
    ret = max(cost0.values()) + max(cost1.values()) + max(cost2.values())
    for i in range(C):
        for j in range(C):
            for k in range(C):
                if i == j or j == k or k == i:
                    continue
                else:
                    ret = min(ret, cost0[i]+cost1[j]+cost2[k])
    return ret


def main():
    N, C = map(int, input().split())
    D = []
    for i in range(C):
        D.append(list(map(int, input().split())))
    c = []
    for i in range(N):
        c.append(list(map(int, input().split())))
    print(run(N, C, D, c))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
d=[list((map(int,input().split()))) for _ in range(m)]
c=[list((map(int,input().split()))) for _ in range(n)]
x=[[[True for _ in range(n)] for _ in range(n)] for _ in range(m)]
for k in range(m):
    for i in range(n):
        for j in range(n):
            if c[i][j]==k+1:
                x[k][i][j]=False
res=[]
for c1 in range(m):
    for c2 in range(m):
        for c3 in range(m):
            if c1==c2 or c2==c3 or c1==c3:
                pass
            else:
                t=0
                for i in range(n):
                    for j in range(n):
                        if (i+j)%3==0:
                            if x[c1][i][j]:
                                t+=d[c[i][j]-1][c1]
                        if (i+j)%3==1:
                            if x[c2][i][j]:
                                t+=d[c[i][j]-1][c2]
                        if (i+j)%3==2:
                            if x[c3][i][j]:
                                t+=d[c[i][j]-1][c3]
                res.append(t)
print(min(res))

Submission status: Time Limit Exceeded

Solution code:
n,c = [int(i) for i in input().split()]
d = []
for i in range(c):
    d.append(list(map(int, input().split())))
color = []
for i in range(n):
    color.append(list(map(int, input().split())))
wrongfeeling = [[0 for i in range(3)] for j in range(c)]
for a in range(c):
    for l in range(n):
        for row in range(n):
            wrongfeeling[a][(l+row)%3] += d[color[row][l]-1][a]
D = wrongfeeling[0][0]+wrongfeeling[1][1]+wrongfeeling[2][2]
for c0 in range (c):
    for c1 in range (c):
        if c1 == c0:
            continue
        for c2 in range (c):
            if c2 == c1 or c2 == c0:
                continue
            D = min(D,wrongfeeling[c0][0]+wrongfeeling[c1][1]+wrongfeeling[c2][2])
print(D)

Submission status: Time Limit Exceeded

Solution code:
n,c = [int(i) for i in input().split()]
d = [] 
for i in range(c):
    d.append(list(map(int, input().split())))
color = []
for i in range(n):
    color.append(list(map(int, input().split())))
for i in range(n):
    for j in range(n):
        color[i][j] -= 1
dofc = [[0 for i in range(3)] for j in range(c)]
for a in range(c):
        for l in range(n):
            for row in range(n):
                dofc[a][(l+row)%3] += d[color[row][l]][a]
D = dofc[0][0]+dofc[1][1]+dofc[2][2]
for c0 in range (c):
    for c1 in range (c):
        if c1 == c0:
            continue
        for c2 in range (c):
            if c2 == c1 or c2 == c0:
                continue
            D = min(D,dofc[c0][0]+dofc[c1][1]+dofc[c2][2])
print(D)

Submission status: Time Limit Exceeded

Solution code:
n,c = [int(i) for i in input().split()]
d = [] 
for i in range(c):
    d.append(list(map(int, input().split())))
color = []
for i in range(n):
    color.append(list(map(int, input().split())))
for i in range(n):
    for j in range(n):
        color[i][j] -= 1
dofc = [[0 for i in range(3)] for j in range(c)]
for t in range(3):
    for a in range(c):
        for l in range(n):
            row = (2*l+t+1)%3
            while row < n:
                dofc[a][t] += d[color[row][l]][a]
                row = row+3
D = dofc[0][0]+dofc[1][1]+dofc[2][2]
for c0 in range (c):
    for c1 in range (c):
        if c1 == c0:
            continue
        for c2 in range (c):
            if c2 == c1 or c2 == c0:
                continue
            D = min(D,dofc[c0][0]+dofc[c1][1]+dofc[c2][2])
print(D)

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)]

D_sum = [[0]*C for _ in range(3)]

for i in range(C):
    for j in range(N):
        for k in range(N):
            D_sum[(j+k)%3][i] += D[c[j][k]-1][i]
            
ans = 1000*500*500
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            else:
                ans = min(ans, D_sum[0][i]+D_sum[1][j]+D_sum[2][k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,c=map(int,input().split())
d=[list(map(int,input().split()))for _ in range(c)]
l=[[i for i in[0]*c]for _ in range(3)]
for i in range(n):
  t=list(map(int,input().split()))
  for j in range(n):
    l[(i+j)%3][t[j]-1]+=1
c=10**18
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i==j or j==k or k==i:continue
      c=min(c,sum(d[x][i]*l[0][x]+d[x][j]*l[1][x]+d[x][k]*l[2][x]for x in range(c)))
print(c)

Submission status: Time Limit Exceeded

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

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

x=[[0]*3 for i in range(c)]
for i in range(n):
    for j in range(n):
        for k in range(c):
            x[k][(i+j)%3]+=d[init[i][j]-1][k]



ans=float('inf')
for i in range(c):
    for j in range(c):
        for k in range(c):
            if i!=j and j!=k and k!=i:
                ans=min(ans,x[i][0]+x[j][1]+x[k][2])

print(ans)

Submission status: Time Limit Exceeded

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

#print(D)

C1=[]
C2=[]
C3=[]
for i in range(n):
    for j in range(n):
        f=(i+j)%3
        if f==0:
            C1.append(C[i][j])
        if f==1:
            C2.append(C[i][j])
        if f==2:
            C3.append(C[i][j])
        

miniwa=1000*500*500

#print(C3)

for c1 in range(0,c):
    iwa1=sum(D[i-1][c1] for i in C1)
    for c2 in range(0,c):
        iwa2=sum(D[j-1][c2] for j in C2)
        for c3 in range(0,c):
            if c1!=c2 and c2!=c3 and c3!=c1 :
                iwa3=sum(D[k-1][c3] for k in C3)
                iwa=iwa1+iwa2+iwa3
                miniwa=min(miniwa,iwa)

print(miniwa)

Submission status: Time Limit Exceeded

Solution code:
def iin(): return int(input())
def nl(): return list(map(int, input().split()))
def ary(r, c, v): return [[v for _ in range(c)] for _ in range(r)]

N, C = nl()
d = [nl() for _ in range(C)]
c = [nl() for _ in range(N)]

ans = float('inf')
for c0 in range(1, C + 1):
    for c1 in range(1, C + 1):
        if c0 == c1:
            continue
        for c2 in range(1, C + 1):
            if c0 == c2 or c1 == c2:
                continue
            cost = 0
            for i in range(N):
                for j in range(N):
                    next_color = [c0, c1, c2][(i + j) % 3]
                    cost += d[c[i][j] - 1][next_color - 1]
            ans = min(ans, cost)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
c = [list(map(int,input().split())) for i in range(N)]
m = N*N*(10**3)
for i in range(C):
  for j in range(C):
    for k in range(C):
      s = m
      if i!=j and j!=k and k!=i:
        s = 0
        for x in range(N):
          for y in range(N):
            if (x+y)%3 == 0:
              s += D[c[x][y]-1][i]
            elif (x+y)%3 == 1:
              s += D[c[x][y]-1][j]
            else:
              s += D[c[x][y]-1][k]
        if s < m:
          m = s
print(m)