Problem:


Score : 100 points

Problem Statement

You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j).
A nonnegative integer A_{i,j} is written for each square (i,j).

You choose some of the squares so that each row and column contains at most K chosen squares.
Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares.
Additionally, calculate a way to choose squares that acheives the maximum.

Constraints

1 \leq N \leq 50

1 \leq K \leq N

0 \leq A_{i,j} \leq 10^9

All values in Input are integer.

Input

Input is given from Standard Input in the following format:

N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}

Output

On the first line, print the maximum value of the sum of the integers written on the chosen squares.

On the next N lines, print a way that achieves the maximum.

Precisely, output the strings t_1,t_2,\cdots,t_N, that satisfies t_{i,j}=X if you choose (i,j) and t_{i,j}=. otherwise.

You may print any way to choose squares that maximizes the sum.

Sample Input 1

3 1
5 3 2
1 4 8
7 6 9

Sample Output 1

19
X..
..X
.X.

Sample Input 2

3 2
10 10 1
10 10 1
1 1 10

Sample Output 2

50
XX.
XX.
..X



Sample input:
3 1
5 3 2
1 4 8
7 6 9


Sample output:
19
X..
..X
.X.

Submission status: Wrong Answer

Solution code:
from heapq import heappop, heappush, heapify

class MinCostFlow():
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, fr, to, cap, cost):
        assert 0 <= fr < self.n
        assert 0 <= to < self.n
        m = len(self.pos)
        self.pos.append((fr, len(self.graph[fr])))
        self.graph[fr].append([to, len(self.graph[to]), cap, cost])
        self.graph[to].append([fr, len(self.graph[fr]) - 1, 0, -cost])
        return m

    def get_edge(self, idx):
        assert 0 <= idx < len(self.pos)
        to, rev, cap, cost = self.graph[self.pos[idx][0]][self.pos[idx][1]]
        rev_to, rev_rev, rev_cap, rev_cost = self.graph[to][rev]
        return self.pos[idx][0], to, cap + rev_cap, rev_cap, cost

    def edges(self):
        for i in range(len(self.pos)):
            yield self.get_edge(i)

    def dual_ref(self, s, t):
        dist = [2**63 - 1] * self.n
        dist[s] = 0
        vis = [0] * self.n
        self.dual = [0] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        queue = []
        heappush(queue, (0, s))
        while queue:
            k, v = heappop(queue)
            if vis[v]: continue
            vis[v] = True
            if v == t: break
            for i in range(len(self.graph[v])):
                to, rev, cap, cost = self.graph[v][i]
                if vis[to] or not cap: continue
                cost += self.dual[v] - self.dual[to]
                if dist[to] - dist[v] > cost:
                    dist[to] = dist[v] + cost
                    self.pv[to] = v
                    self.pe[to] = i
                    heappush(queue, (dist[to], to))
        if not vis[t]: return False
        for v in range(self.n):
            if not vis[v]: continue
            self.dual[v] -= dist[t] - dist[v]
        return True

    def flow(self, s, t):
        return self.flow_with_limit(s, t, 2**63 - 1)

    def flow_with_limit(self, s, t, limit):
        return self.slope_with_limit(s, t, limit)[-1]

    def slope(self, s, t):
        return self.slope_with_limit(s, t, 2**63 - 1)

    def slope_with_limit(self, s, t, limit):
        assert 0 <= s < self.n
        assert 0 <= t < self.n
        assert s != t
        flow = 0
        cost = 0
        prev_cost = -1
        res = []
        while flow < limit:
            if not self.dual_ref(s, t): break
            c = limit - flow
            v = t
            while v != s:
                c = min(c, self.graph[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                to, rev, cap, _ = self.graph[self.pv[v]][self.pe[v]]
                self.graph[self.pv[v]][self.pe[v]][2] -= c
                self.graph[v][rev][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                res.pop()
            res.append((flow, cost))
            prev_cost = cost
        return res

N, K = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(N)]

MAX = sum(map(sum, A)) + 1

mcf = MinCostFlow(2 * N + 2)
mcf.add_edge(2 * N, 2 * N + 1, N * K, MAX)

for i in range(N):
    mcf.add_edge(2 * N, i, K, 0)
    mcf.add_edge(i + N, 2 * N + 1, K, 0)
    for j in range(N):
        mcf.add_edge(i, j + N, 1, MAX - A[i][j])

print(N * K * MAX - mcf.flow_with_limit(2 * N, 2 * N + 1, N * K)[1])

res = [['.' for j in range(N)] for i in range(N)]

for fr, to, cap, flow, cost in mcf.edges():
    if flow == 0 or fr == 2 * N or to == 2 * N + 1:
        continue
    res[fr][to - N] = 'X'

for r in res:
    print(''.join(r))

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N)]

import heapq
class MinCostFlow:
    def __init__(self, n):
        self.n = n
        self.es = [[] for _ in range(n)] #[[to,rev,cap,cost], ...]
        self.pos = []

    def add_edge(self, fr, to, cap, cost):
        m = len(self.pos)
        self.pos.append((fr, len(self.es[fr])))
        self.es[fr].append([to, len(self.es[to]), cap, cost])
        self.es[to].append([fr, len(self.es[fr])-1, 0, -cost])
        return m

    def get_edges(self):
        ret = []
        for fr,i in self.pos:
            to,rev,cap,cost = self.es[fr][i]
            flow = self.es[to][rev][2]
            cap += flow
            ret.append((fr, to, cap, flow, cost))
        return ret

    def flow(self, s, t, flow_limit=2**63):
        return self.slope(s,t,flow_limit)[-1]

    def slope(self, s, t, flow_limit=2**63):
        self.dual = [0] * self.n
        self.dist = [2**63] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n
        def _dual_ref():
            self.dist = [2**63] * self.n
            self.pv = [-1] * self.n
            self.pe = [-1] * self.n
            self.vis = [False] * self.n
            hq = [(0,s)]
            self.dist[s] = 0
            while hq:
                p = heapq.heappop(hq)
                v = p[1]
                if self.vis[v]: continue
                self.vis[v] = True
                if v==t: break
                for i,(to,rev,cap,cost) in enumerate(self.es[v]):
                    if self.vis[to] or not cap: continue
                    _cost = cost - self.dual[to] + self.dual[v]
                    if self.dist[to] - self.dist[v] > _cost:
                        self.dist[to] = self.dist[v] + _cost
                        self.pv[to] = v
                        self.pe[to] = i
                        heapq.heappush(hq, (self.dist[to],to))
            if not self.vis[t]:
                return False
            for v in range(self.n):
                if not self.vis[v]: continue
                self.dual[v] -= self.dist[t] - self.dist[v]
            return True
        flow, cost, prev_cost = 0, 0, -1
        ret = [(flow, cost)]
        while flow < flow_limit:
            if not _dual_ref(): break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.es[self.pv[v]][self.pe[v]][2])
                v = self.pv[v]
            v = t
            while v != s:
                self.es[self.pv[v]][self.pe[v]][2] -= c
                self.es[v][self.es[self.pv[v]][self.pe[v]][1]][2] += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                ret.pop()
            ret.append((flow, cost))
            prev_cost = cost
        return ret

mcf = MinCostFlow(2*N + 2)
src,dst = 2*N, 2*N+1

BIG = 10**9
mcf.add_edge(src, dst, N+K, BIG)
for i in range(N):
    mcf.add_edge(src, i, K, 0)
    mcf.add_edge(N+i, dst, K, 0)
for i,row in enumerate(A):
    for j,a in enumerate(row):
        mcf.add_edge(i, N+j, 1, BIG - a)

_,mincost = mcf.flow(src, dst, N*K)
ans = [['.']*N for _ in range(N)]
print(N*K*BIG - mincost)
for fr,to,cap,flow,cost in mcf.get_edges():
    if fr == src or to == dst or flow == 0: continue
    ans[fr][to - N] = 'X'
for row in ans:
    print(''.join(row))

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class MinCostFlow:
    """ 最小費用流(ダイクストラ版)：O(F*E*logV) """

    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.pos = []

    def copy(self):
        res = MinCostFlow(self.N)
        res.G = [[a[:] for a in b] for b in self.G]
        res.pos = [a[:] for a in self.pos]
        return res

    def add_edge(self, fr, to, cap, cost):
        self.pos.append((fr, len(self.G[fr])))
        self.G[fr].append([to, cap, cost, len(self.G[to])])
        self.G[to].append([fr, 0, -cost, len(self.G[fr])-1])

    def flow(self, s, t, f):
        from heapq import heappush, heappop

        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        H = [0] * N
        prv_v = [0] * N
        prv_e = [0] * N

        while f:
            dist = [INF] * N
            dist[s] = 0
            que = [(0, s)]

            while que:
                c, v = heappop(que)
                if dist[v] < c:
                    continue
                for i, (to, cap, cost, _) in enumerate(G[v]):
                    if cap > 0 and dist[to] > dist[v] + cost + H[v] - H[to]:
                        dist[to] = r = dist[v] + cost + H[v] - H[to]
                        prv_v[to] = v; prv_e[to] = i
                        heappush(que, (r, to))
            if dist[t] == INF:
                return INF

            for i in range(N):
                H[i] += dist[i]

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * H[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

    def get_edge(self, i):
        e = self.G[self.pos[i][0]][self.pos[i][1]]
        re = self.G[e[0]][e[3]]
        # from, to, cap, flow, cost
        return (self.pos[i][0], e[0], e[1]+re[1], re[1], e[2])

    def get_edges(self):
        M = len(self.pos)
        res = []
        for i in range(M):
            res.append(self.get_edge(i))
        return res


def trisearch_min(lo, hi, func):
    """ 三分探索 """

    while lo+2 < hi:
        m1 = (lo*2+hi) // 3
        m2 = (lo+hi*2) // 3
        res1 = func(m1)
        res2 = func(m2)
        if res1 <= res2:
            hi = m2
        else:
            lo = m1
    return m1, m2

N, K = MAP()
grid = [[] for i in range(N)]
for i in range(N):
    grid[i] = LIST()

offset = 10**12
mcf = MinCostFlow(N*2+2)
s = N*2
t = N*2 + 1
for i in range(N):
    mcf.add_edge(s, i, K, offset)
    mcf.add_edge(N+i, t, K, offset)
    for j in range(N):
        mcf.add_edge(i, N+j, 1, offset-grid[i][j])

def check(x):
    global mcf

    tmp = mcf.copy()
    res = mcf.flow(s, t, x)
    res -= offset * x * 3
    mcf = tmp
    return res

m1, m2 = trisearch_min(-1, N*N+1, check)
x = m1 if check(m1) <= check(m2) else m2

mn = mcf.flow(s, t, x)
mn -= offset * x * 3
ans = [['.' for j in range(N)] for i in range(N)]
edges = mcf.get_edges()
for fr, to, cap, f, c in edges:
    if fr != s and to != t and f:
        h = fr
        w = to - N
        ans[h][w] = 'X'
print(-mn)
for i in range(N):
    print(''.join(ans[i]))

Submission status: Wrong Answer

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10**9)
INF = 10**19
MOD = 10**9 + 7
EPS = 10**-10

class MinCostFlow:
    """ 最小費用流(ベルマンフォード版、負コストに対応可)：O(F*E*V) """

    INF = 10**18

    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]
        self.pos = []
    
    def copy(self):
        res = MinCostFlow(self.N)
        res.G = [[a[:] for a in b] for b in self.G]
        res.pos = [a[:] for a in self.pos]
        return res

    def add_edge(self, fr, to, cap, cost):
        self.pos.append((fr, len(self.G[fr])))
        self.G[fr].append([to, cap, cost, len(self.G[to])])
        self.G[to].append([fr, 0, -cost, len(self.G[fr])-1])

    def flow(self, s, t, f):

        N = self.N; G = self.G
        INF = MinCostFlow.INF

        res = 0
        prv_v = [0] * N
        prv_e = [0] * N

        while f:
            dist = [INF] * N
            dist[s] = 0
            update = True

            while update:
                update = False
                for v in range(N):
                    if dist[v] == INF:
                        continue
                    for i, (to, cap, cost, _) in enumerate(G[v]):
                        if cap > 0 and dist[to] > dist[v] + cost:
                            dist[to] = dist[v] + cost
                            prv_v[to] = v; prv_e[to] = i
                            update = True
            if dist[t] == INF:
                return INF

            d = f; v = t
            while v != s:
                d = min(d, G[prv_v[v]][prv_e[v]][1])
                v = prv_v[v]
            f -= d
            res += d * dist[t]
            v = t
            while v != s:
                e = G[prv_v[v]][prv_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = prv_v[v]
        return res

    def get_edge(self, i):
        e = self.G[self.pos[i][0]][self.pos[i][1]]
        re = self.G[e[0]][e[3]]
        # from, to, cap, flow, cost
        return (self.pos[i][0], e[0], e[1]+re[1], re[1], e[2])

    def get_edges(self):
        M = len(self.pos)
        res = []
        for i in range(M):
            res.append(self.get_edge(i))
        return res

N, K = MAP()
grid = [[] for i in range(N)]
for i in range(N):
    grid[i] = LIST()

mcf = MinCostFlow(N*2+2)
s = N*2
t = N*2 + 1
for i in range(N):
    mcf.add_edge(s, i, K, 0)
    mcf.add_edge(N+i, t, K, 0)
    for j in range(N):
        mcf.add_edge(i, N+j, 1, -grid[i][j])

mx = 0
for x in range(1, N*N+1):
    tmp = mcf.copy()
    res = -mcf.flow(s, t, x)
    if res > mx:
        mx = res
        ans = [['.' for j in range(N)] for i in range(N)]
        edges = mcf.get_edges()
        for fr, to, cap, f, c in edges:
            if fr != s and to != t and f:
                h = fr
                w = to - N
                ans[h][w] = 'x'
    else:
        break
    mcf = tmp
print(mx)
for i in range(N):
    print(''.join(ans[i]))

Submission status: Wrong Answer

Solution code:
import os
import sys
from heapq import heappop, heappush

import numpy as np


def solve(n, k, aaa):
    MINCOSTFLOW_LINKS = []
    MINCOSTFLOW_LINK_INDICES = []
    MINCOSTFLOW_CURRENT_LINK_INDEX = []
    INF = 10 ** 10

    def mincostflow_init(m):
        """ m:辺数(逆辺除く) """
        MINCOSTFLOW_LINKS.append(np.zeros((m * 2, 5), np.int64))
        MINCOSTFLOW_CURRENT_LINK_INDEX.append(0)
        return len(MINCOSTFLOW_LINKS) - 1

    def mincostflow_add_link(ins, frm, to, capacity, cost):
        links = MINCOSTFLOW_LINKS[ins]
        li = MINCOSTFLOW_CURRENT_LINK_INDEX[ins]
        links[li] = (frm, to, capacity, cost, li + 1)
        links[li + 1] = (to, frm, 0, -cost, li)
        MINCOSTFLOW_CURRENT_LINK_INDEX[ins] += 2

    def mincostflow_fix_link(ins, n):
        links = MINCOSTFLOW_LINKS[ins]
        sort_idx = np.argsort(links[:, 0])
        links[links[sort_idx, 4], 4] = np.arange(sort_idx.size)
        links = links[sort_idx]

        MINCOSTFLOW_LINK_INDICES.append(np.searchsorted(links[:, 0], np.arange(n + 1)))
        MINCOSTFLOW_LINKS[ins] = links

    def mincostflow_flow(ins, s, t, quantity):
        links = MINCOSTFLOW_LINKS[ins]
        link_indices = MINCOSTFLOW_LINK_INDICES[ins]
        n = len(links)
        res = 0
        potentials = np.zeros(n, dtype=np.int64)
        dist = np.full(n, INF, dtype=np.int64)
        prev_v = np.full(n, -1, dtype=np.int64)
        prev_e = np.full(n, -1, dtype=np.int64)

        while quantity:
            dist.fill(INF)
            dist[s] = 0
            que = [(0, s)]

            while que:
                total_cost, v = heappop(que)
                if dist[v] < total_cost:
                    continue
                for li in range(link_indices[v], link_indices[v + 1]):
                    _, u, cap, cost, _ = links[li]
                    new_cost = dist[v] + potentials[v] - potentials[u] + cost
                    if cap > 0 and new_cost < dist[u]:
                        dist[u] = new_cost
                        prev_v[u] = v
                        prev_e[u] = li
                        heappush(que, (new_cost, u))

            # Cannot flow required quantity
            if dist[t] == INF:
                return -1

            potentials += dist

            cur_flow = quantity
            v = t
            while v != s:
                cur_flow = min(cur_flow, links[prev_e[v]][2])
                v = prev_v[v]
            quantity -= cur_flow
            res += cur_flow * potentials[t]

            v = t
            while v != s:
                link = links[prev_e[v]]
                link[2] -= cur_flow
                links[link[4]][2] += cur_flow
                v = prev_v[v]

        return res

    ins = mincostflow_init(n ** 2 + n * 2 + 1)
    s = n + n
    t = s + 1

    mincostflow_add_link(ins, s, t, n * k, INF)
    for i in range(n):
        mincostflow_add_link(ins, s, i, k, 0)
        mincostflow_add_link(ins, i + n, t, k, 0)
        for j in range(n):
            mincostflow_add_link(ins, i, j + n, 1, INF - aaa[i][j])
    mincostflow_fix_link(ins, n * 2 + 2)

    ans = INF * (n * k) - mincostflow_flow(ins, s, t, n * k)

    matrix = np.zeros((n, n), dtype=np.int8)
    links = MINCOSTFLOW_LINKS[ins]
    link_indices = MINCOSTFLOW_LINK_INDICES[ins]
    for i in range(n):
        for li in range(link_indices[i], link_indices[i + 1]):
            link = links[li]
            if link[1] == t or link[2] == 1 or link[3] <= 0:
                continue
            j = link[1] - n
            matrix[i][j] = 1

    return ans, matrix


SIGNATURE = '(i8,i8,i8[:,:],)'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)

n, k = map(int, sys.stdin.readline().split())
aaa = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ').reshape(n, n)
ans, matrix = solve(n, k, aaa)

print(ans)
np.savetxt(sys.stdout.buffer, np.vectorize('.X'.__getitem__)(matrix), fmt='%s', delimiter='')

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.optimize
import scipy.sparse

N, K = [int(x) for x in input().split()]
A = [[int(x) for x in input().split()] for i in range(N)]
A = np.array(A)

M = scipy.sparse.lil_matrix((N + N, N * N))
for i in range(N):
    M[i, N * i : N * i + N] = 1
    M[i + N, i : N * N : N] = 1


# minimize sum -A_ij * x_ij
#   sum_j x_ij <= K   for all i
#   sum_i x_ij <= K   for all j
#         x_ij in {0, 1}
res = scipy.optimize.linprog(
    c=-np.ravel(A), A_ub=M, b_ub=K * np.ones(N + N), bounds=(0, 1)
)
x = np.round(res.x)

print(int(round(np.ravel(A) @ x)))
x = x.reshape(N, N)

grid = [["." for c in range(N)] for r in range(N)]
for r in range(N):
    for c in range(N):
        if x[r][c]:
            grid[r][c] = "X"

for row in grid:
    print("".join(row))

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.optimize

N, K = [int(x) for x in input().split()]
A = [[int(x) for x in input().split()] for i in range(N)]
A = np.array(A)

M = np.zeros((N + N, N * N))
for i in range(N):
    M[i, N * i : N * i + N] = 1
    M[i + N, i : N * N : N] = 1


# minimize sum -A_ij * x_ij
#   sum_j x_ij <= K   for all i
#   sum_i x_ij <= K   for all j
#         x_ij in {0, 1}
res = scipy.optimize.linprog(
    c=-np.ravel(A), A_ub=M, b_ub=K * np.ones(N + N), bounds=(0, 1),
)
x = np.round(res.x)

print(int(round(np.ravel(A) @ x)))
x = x.reshape(N, N)

grid = [["." for c in range(N)] for r in range(N)]
for r in range(N):
    for c in range(N):
        if x[r][c]:
            grid[r][c] = "X"

for row in grid:
    print("".join(row))

Submission status: Wrong Answer

Solution code:
import numpy as np
import scipy.optimize

N, K = [int(x) for x in input().split()]
A = [[int(x) for x in input().split()] for i in range(N)]
A = np.array(A)

M = np.zeros((N + N, N * N))
for i in range(N):
    M[i, N * i : N * i + N] = 1
    M[i + N, i : N * N : N] = 1


# minimize sum -A_ij * x_ij
#   sum_j x_ij <= K   for all i
#   sum_i x_ij <= K   for all j
#         x_ij in {0, 1}
res = scipy.optimize.linprog(
    c=-np.ravel(A), A_ub=M, b_ub=K * np.ones(N + N), bounds=(0, 1),
)
x = np.round(res.x)

print(round(np.ravel(A) @ x))
x = x.reshape(N, N)

grid = [["." for c in range(N)] for r in range(N)]
for r in range(N):
    for c in range(N):
        if x[r][c]:
            grid[r][c] = "X"

for row in grid:
    print("".join(row))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
class MinCostFlowwithDijkstra:
    INF = 1<<60
    
    def __init__(self, N):
        self.N = N
        self.Edge = [[] for _ in range(N)]
    
    def add_edge(self, st, en, cap, cost):
        self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
        self.Edge[en].append([st, 0, -cost, len(self.Edge[st])-1])
    
    def get_mf(self, so, si, fl):
        N = self.N
        INF = self.INF
        res = 0
        Pot = [0]*N
        geta = N
        
        
        prv = [None]*N
        prenum = [None]*N
        while fl:
            dist = [INF]*N
            dist[so] = 0
            Q = [so]
            
            while Q:
                cost, vn = divmod(hpp(Q), geta)
                if dist[vn] < cost:
                    continue
                
                for enum in range(len(self.Edge[vn])):
                    vf, cap, cost, _ = self.Edge[vn][enum]
                    cc = dist[vn] + cost - Pot[vn] + Pot[vf]
                    if cap > 0 and dist[vf] > cc:
                        dist[vf] = cc
                        prv[vf] = vn
                        prenum[vf] = enum
                        hp(Q, cc*geta + vf)
            
            if dist[si] == INF:
                return -1
            
            for i in range(N):
                Pot[i] -= dist[i]
            
            cfl = fl
            vf = si
            while vf != so:
                cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
                vf = prv[vf]
            
            fl -= cfl
            res -= cfl*Pot[si]
            vf = si
            while vf != so:
                e = self.Edge[prv[vf]][prenum[vf]]
                e[1] -= cfl
                self.Edge[vf][e[3]][1] += cfl
                vf = prv[vf]
        return res


N, K = map(int, readline().split())

MAX = 10**9+7

A = [list(map(int, readline().split())) for _ in range(N)]

T = MinCostFlowwithDijkstra(2*N+2)

st = 2*N
en = st+1

for i in range(N):
    T.add_edge(st, i, K, 0)
    T.add_edge(N+i, en, K, 0)

for i in range(N):
    for j in range(N):
        T.add_edge(i, N+j, 1, MAX-A[i][j])

ff = N//K * K*K + (N%K)**2 

print(ff*MAX - T.get_mf(st, en, ff))
dot = ord('.')
cross = ord('X')
Ans = [[dot]*N for _ in range(N)]

cnt = 0
for j in range(N):
    for vf, cap, _, _ in T.Edge[N+j]:
        if cap == 1 and vf != en:
            Ans[vf][j] = cross
            cnt += 1
assert cnt == ff
print('\n'.join(''.join(map(chr, a)) for a in Ans))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp
class MinCostFlowwithDijkstra:
    INF = 1<<60
    
    def __init__(self, N):
        self.N = N
        self.Edge = [[] for _ in range(N)]
    
    def add_edge(self, st, en, cap, cost):
        self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
        self.Edge[en].append([st, 0, -cost, len(self.Edge[st])-1])
    
    def get_mf(self, so, si, fl):
        N = self.N
        INF = self.INF
        res = 0
        Pot = [0]*N
        geta = N
        
        
        prv = [None]*N
        prenum = [None]*N
        while fl:
            dist = [INF]*N
            dist[so] = 0
            Q = [so]
            
            while Q:
                cost, vn = divmod(hpp(Q), geta)
                if dist[vn] < cost:
                    continue
                
                for enum in range(len(self.Edge[vn])):
                    vf, cap, cost, _ = self.Edge[vn][enum]
                    cc = dist[vn] + cost - Pot[vn] + Pot[vf]
                    if cap > 0 and dist[vf] > cc:
                        dist[vf] = cc
                        prv[vf] = vn
                        prenum[vf] = enum
                        hp(Q, cc*geta + vf)
            
            if dist[si] == INF:
                return -1
            
            for i in range(N):
                Pot[i] -= dist[i]
            
            cfl = fl
            vf = si
            while vf != so:
                cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
                vf = prv[vf]
            
            fl -= cfl
            res -= cfl*Pot[si]
            vf = si
            while vf != so:
                e = self.Edge[prv[vf]][prenum[vf]]
                e[1] -= cfl
                self.Edge[vf][e[3]][1] += cfl
                vf = prv[vf]
        return res


N, K = map(int, readline().split())

MAX = 10**9+7

A = [list(map(int, readline().split())) for _ in range(N)]

T = MinCostFlowwithDijkstra(2*N+2)

st = 2*N
en = st+1

for i in range(N):
    T.add_edge(st, i, K, 0)
    T.add_edge(N+i, en, K, 0)

for i in range(N):
    for j in range(N):
        T.add_edge(i, N+j, 1, MAX-A[i][j])

ff = N//K * K*K + (N%K)**2 

print(ff*MAX - T.get_mf(st, en, ff))
dot = ord('.')
cross = ord('X')
Ans = [[dot]*N for _ in range(N)]

for j in range(N):
    for vf, cap, _, _ in T.Edge[N+j]:
        if cap == 1 and vf != en:
            Ans[vf][j] = cross

print('\n'.join(''.join(map(chr, a)) for a in Ans))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
V=2*N+2
INF=10**14
G=[[] for i in range(V)]
D=[INF]*V
PV,PE=[0]*V,[0]*V
def ae(fr,to,ca,co):
  global G
  G[fr].append([to,ca,co,len(G[to]),0])
  G[to].append([fr,0,-co,len(G[fr])-1,0])

def mcf(s,t,f):
  global G,V,INF,D,PV,PE
  for i in range(V):
    for j in range(len(G[i])):
      G[i][j][4]=0
  r=0
  z=f
  while z>0:
    D=[INF]*V
    D[s]=0
    ud=True
    while ud:
      ud=False
      for x in range(V):
        if D[x]==INF:
          continue
        for i in range(len(G[x])):
          if G[x][i][1]>0 and D[G[x][i][0]]>D[x]+G[x][i][2]:
            D[G[x][i][0]]=D[x]+G[x][i][2]
            PV[G[x][i][0]]=x
            PE[G[x][i][0]]=i
            ud=True
    if D[t]==INF:
      return -INF
    d=z
    x=t
    while x!=s:
      d=min(d,G[PV[x]][PE[x]][1])
      x=PV[x]
    z-=d
    r+=d*D[t]
    x=t
    while x!=s:
      G[PV[x]][PE[x]][1]-=d
      G[PV[x]][PE[x]][4]+=d
      G[x][G[PV[x]][PE[x]][3]][1]+=d
      G[x][G[PV[x]][PE[x]][3]][4]-=d
      x=PV[x]
  return r

s=N*2
t=s+1
for i in range(N):
  ae(s,i,K,0)
  ae(N+i,t,K,0)
  for j in range(N):
    ae(i,N+j,1,10**10-A[i][j])
ae(s,t,N*K,10**10)
print(N*K*10**10-mcf(s,t,N*K))
P=[['.']*N for i in range(N)]
for i in range(N):
  for j in range(len(G[i])):
    if G[i][j][4]>0:
      P[i][G[i][j][0]-N]='X'
  print(''.join(P[i]))