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: Accepted

Solution code:
code = r"""
# distutils: language=c++
# distutils: include_dirs=[/home/contestant/.local/lib/python3.8/site-packages/numpy/core/include,/opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False
from libcpp cimport bool
from libcpp.string cimport string
from libcpp.vector cimport vector
from libcpp.pair cimport pair
cdef extern from *:
    ctypedef int MOD "998244353"
    ctypedef long long ll "long long"

cdef extern from "<atcoder/fenwicktree>" namespace "atcoder":
    cdef cppclass fenwick_tree[T]:
        fenwick_tree(int n)
        void add(int p, T x)
        T sum(int l, int r)
cdef class fenwick_tree_:
    cdef fenwick_tree[int] *ptr
    def __cinit__(self, int n): self.ptr = new fenwick_tree[int](n)  
    def __dealloc__(self): del self.ptr
    cpdef void add(self, int p, ll x): self.ptr.add(p, x)
    cpdef ll sum(self, int l, int r): return self.ptr.sum(l, r)

cdef extern from "<atcoder/string>" namespace "atcoder":
    vector[int] suffix_array(vector[int] s, int upper)
    vector[int] suffix_array(vector[ll] s)
    vector[int] suffix_array(string s)
    vector[int] lcp_array(vector[ll] s, vector[int] sa)
    vector[int] lcp_array(string s, vector[int] sa)
    vector[int] z_algorithm(vector[ll] s)
    vector[int] z_algorithm(string s)
cpdef vector[int] suffix_array_u(vector[int] s, int upper): return suffix_array(s, upper)
cpdef vector[int] suffix_array_l(vector[ll] s): return suffix_array(s)
cpdef vector[int] suffix_array_s(string s): return suffix_array(s)
cpdef vector[int] lcp_array_l(vector[ll] s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] lcp_array_s(string s, vector[int] sa): return lcp_array(s, sa)
cpdef vector[int] z_algorithm_l(vector[ll] s): return z_algorithm(s)
cpdef vector[int] z_algorithm_s(string s): return z_algorithm(s)

cdef extern from "<atcoder/convolution>" namespace "atcoder":
    vector[ll] convolution[m](vector[ll] a, vector[ll] b)
    vector[ll] convolution_ll(vector[ll] a, vector[ll] b)
cpdef vector[ll] convolution_(vector[ll] a, vector[ll] b): return convolution[MOD](a, b)
cpdef vector[ll] convolution_ll_(vector[ll] a, vector[ll] b): return convolution_ll(a, b)

cdef extern from "<atcoder/dsu>" namespace "atcoder":
    cpdef cppclass dsu:
        dsu(int n)
        int merge(int a, int b)
        bool same(int a, int b)
        int leader(int a)
        int size(int a)
        vector[vector[int]] groups()
cdef class dsu_:
    cdef dsu *ptr
    def __cinit__(self, int n): self.ptr = new dsu(n)
    def __dealloc__(self): del self.ptr
    cpdef int merge(self,a,b): return self.ptr.merge(a,b)
    cpdef bool same(self,a,b): return self.ptr.same(a,b)
    cpdef int leader(self,a): return self.ptr.leader(a)
    cpdef int size(self,a): return self.ptr.size(a)
    cpdef vector[vector[int]] groups(self): return self.ptr.groups()

cdef extern from "<atcoder/maxflow>" namespace "atcoder":
    cdef cppclass mf_graph[Cap]:
        mf_graph(int n)
        int add_edge(int frm, int to, Cap cap)
        Cap flow(int s, int t)
        Cap flow(int s, int t, Cap flow_limit)
        vector[bool] min_cut(int s)
        cppclass edge:
            int frm "from", to
            Cap cap, flow
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
        void change_edge(int i, Cap new_cap, Cap new_flow)
cdef class mf_graph_:
    cdef mf_graph[ll] *ptr
    def __cinit__(self, int n): self.ptr = new mf_graph[ll](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, ll cap): return self.ptr.add_edge(frm, to, cap)
    cpdef ll flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef ll flow_limit(self, int s, int t, ll flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[bool] min_cut(self, int s): return self.ptr.min_cut(s)
    cpdef vector[ll] get_edge(self, int i):
        cdef mf_graph[ll].edge *e = new mf_graph[ll].edge(self.ptr.get_edge(i))
        cdef vector[ll] *ret_e = new vector[ll]()        
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        return ret_e[0]
    cpdef vector[vector[ll]] edges(self):
        cdef vector[mf_graph[ll].edge] es = self.ptr.edges()
        cdef vector[vector[ll]] *ret_es = new vector[vector[ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
        return ret_es[0]
    cpdef void change_edge(self, int i, ll new_cap, ll new_flow): self.ptr.change_edge(i, new_cap, new_flow)

cdef extern from "<atcoder/mincostflow>" namespace "atcoder":
    cdef cppclass mcf_graph[Cap, Cost]:
        mcf_graph(int n)
        int add_edge(int frm, int to, Cap cap, Cost cost)
        pair[Cap, Cost] flow(int s, int t)
        pair[Cap, Cost] flow(int s, int t, Cap flow_limit)
        vector[pair[Cap, Cost]] slope(int s, int t)
        vector[pair[Cap, Cost]] slope(int s, int t, Cap flow_limit)
        cppclass edge:
            int frm "from", to
            Cap cap, flow
            Cost cost
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()
cdef class mcf_graph_:
    cdef mcf_graph[ll, ll] *ptr
    def __cinit__(self, int n): self.ptr = new mcf_graph[ll, ll](n)  
    def __dealloc__(self): del self.ptr
    cpdef int add_edge(self, int frm, int to, ll cap, ll cost): return self.ptr.add_edge(frm, to, cap, cost)
    cpdef pair[ll, ll] flow(self, int s, int t): return self.ptr.flow(s, t)
    cpdef pair[ll, ll] flow_limit(self, int s, int t, ll flow_limit): return self.ptr.flow(s, t, flow_limit)
    cpdef vector[pair[ll, ll]] slope(self, int s, int t): return self.ptr.slope(s, t)
    cpdef vector[pair[ll, ll]] slope_limit(self, int s, int t, ll flow_limit): return self.ptr.slope(s, t, flow_limit)
    cpdef vector[ll] get_edge(self, int i):
        cdef mcf_graph[ll, ll].edge *e = new mcf_graph[ll, ll].edge(self.ptr.get_edge(i))
        cdef vector[ll] *ret_e = new vector[ll]()
        ret_e.push_back(e.frm)
        ret_e.push_back(e.to)
        ret_e.push_back(e.cap)
        ret_e.push_back(e.flow)
        ret_e.push_back(e.cost)
        return ret_e[0]
    cpdef vector[vector[ll]] edges(self):
        cdef vector[mcf_graph[ll, ll].edge] es = self.ptr.edges()
        cdef vector[vector[ll]] *ret_es = new vector[vector[ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).push_back(es.at(i).frm)
            ret_es.at(i).push_back(es.at(i).to)
            ret_es.at(i).push_back(es.at(i).cap)
            ret_es.at(i).push_back(es.at(i).flow)
            ret_es.at(i).push_back(es.at(i).cost)
        return ret_es[0]

cdef extern from "<atcoder/scc>" namespace "atcoder":
    cdef cppclass scc_graph:
        scc_graph(int n)
        void add_edge(int fr, int to)
        vector[vector[int]] scc()
cdef class scc_graph_:
    cdef scc_graph *ptr
    def __cinit__(self, int n): self.ptr = new scc_graph(n)  
    def __dealloc__(self): del self.ptr
    cpdef void add_edge(self, int fr, int to): self.ptr.add_edge(fr, to)
    cpdef vector[vector[int]] scc(self): return self.ptr.scc()

cdef extern from "<atcoder/twosat>" namespace "atcoder":
    cdef cppclass two_sat:
        two_sat(int n)
        void add_clause(int i, bool f, int j, bool g)
        bool satisfiable()
        vector[bool] answer()
cdef class two_sat_:
    cdef two_sat *ptr
    def __cinit__(self, int n): self.ptr = new two_sat(n)
    def __dealloc__(self): del self.ptr
    cpdef void add_clause(self, int i, bool f, int j, bool g): self.ptr.add_clause(i, f, j, g)
    cpdef bool satisfiable(self): return self.ptr.satisfiable()
    cpdef vector[bool] answer(self): return self.ptr.answer()
"""

import os
try:
    from atcoder import *
except:
    open('atcoder.pyx', 'w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')

X=10**9
N,K=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
g=mcf_graph_(2*N+2)
s,t=2*N,2*N+1
g.add_edge(s,t,N*K,X)
for i in range(N):
    g.add_edge(s,i,K,0)
    g.add_edge(N+i,t,K,0)
    for j in range(N):
        g.add_edge(i,N+j,1,X-A[i][j])
r=g.flow_limit(s,t,N*K)
print(N*K*X-r[1])
l=[['.' for j in range(N)] for i in range(N)]
for frm,to,cap,flow,cost in g.edges():
    if frm<s and to<t and 0<flow:
        l[frm][to-N]='X'
print('\n'.join([''.join(line) for line in l]))

Submission status: Accepted

Solution code:
header_code = """
#include "/opt/atcoder-stl/atcoder/internal_bit.hpp"
#include "/opt/atcoder-stl/atcoder/lazysegtree.hpp"
#include "/opt/atcoder-stl/atcoder/modint.hpp"
#include <vector>
#include <algorithm>
#include <cassert>

namespace aclython {

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
  public:
    segtree() : segtree(0) {}
    segtree(int n) : segtree(std::vector<S>(n, e())) {}
    segtree(const std::vector<S>& v) : _n(int(v.size())) {
        log = atcoder::internal::ceil_pow2(_n);
        size = 1 << log;
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    template <bool (*f)(S)> int max_right(int l, S b) {
        return max_right(l, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int max_right(int l, S b, F f) {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]), b)) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]), b)) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r, S b) {
        return min_left(r, b, [](S x, S y) { return f(x, y); });
    }
    template <class F> int min_left(int r, S b, F f) {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm), b)) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm), b)) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};



int min_op(int n, int m){
    return std::min(n, m);
}

int min_e(){
    return (int)1e9;
}

struct segtree_min {
    public:
        segtree_min() : segtree_min(0) {}
        segtree_min(int n) : segtree_min(std::vector<int>(n, min_e())) {}
        segtree_min(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, min_op, min_e> seg;
};

int max_op(int n, int m){
    return std::max(n, m);
}

int max_e(){
    return 0;
}

struct segtree_max {
    public:
        segtree_max() : segtree_max(0) {}
        segtree_max(int n) : segtree_max(std::vector<int>(n, max_e())) {}
        segtree_max(const std::vector<int>& vec) : seg(vec) {}

        void set(int p, int x) {seg.set(p, x);}
        int get(int p) {return seg.get(p);}
        int prod(int l, int r) {return seg.prod(l, r);}
        int all_prod() {return seg.all_prod();}

        int max_right(int l, int v) {return seg.max_right(l, v, [](int x, int y) { return x<y; });}
        int min_left(int r, int v) {return seg.min_left(r, v, [](int x, int y) { return x<y; });}

    private:
        segtree<int, max_op, max_e> seg;
};

using mint = atcoder::modint998244353;

struct S {
    mint a;
    int size;
    S(mint _a, int _size) : a(_a) ,size(_size) {}
    S(int _a, int _size) : a(_a) ,size(_size) {}
    S(const S &s) : a(s.a), size(s.size) {}
    int get_a() { return (int)a.val(); }
};

struct F {
    mint a, b;
    F(mint _a, mint _b) : a(_a), b(_b) {}
    F(int _a, int _b) : a(_a), b(_b) {}
    F(const F &f) : a(f.a), b(f.b) {}
    int get_a() { return (int)a.val(); }
    int get_b() { return (int)b.val(); }
};

S op(S l, S r) { return S{l.a + r.a, l.size + r.size}; }

S e() { return S{0, 0}; }

S mapping(F l, S r) { return S{r.a * l.a + r.size * l.b, r.size}; }

F composition(F l, F r) { return F{r.a * l.a, r.b * l.a + l.b}; }

F id() { return F{1, 0}; }

struct lazy_segtree{
    lazy_segtree() : lazy_segtree(0) {}
    lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    lazy_segtree(const std::vector<S>& vec) : seg(vec) {}
    void set(int p, S x) { seg.set(p, x); }
    S get(int p) { return seg.get(p); }
    S prod(int l, int r) { return seg.prod(l, r); }
    S all_prod() { return seg.all_prod(); }
    void apply(int p, F f) { seg.apply(p, f); }
    void apply(int l, int r, F f) { seg.apply(l, r, f); }
    private:
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg;
};

}
"""

code = """

# distutils: language=c++
# distutils: include_dirs=[/home/USERNAME/.local/lib/python3.8/site-packages/numpy/core/include, /opt/atcoder-stl]
# cython: boundscheck=False
# cython: wraparound=False

from libc.stdio cimport getchar, printf
from libcpp.vector cimport vector
from libcpp.utility cimport pair
from libcpp.string cimport string
cpdef inline vector[int] ReadInt(int n):
    cdef int b, c
    cdef vector[int] *v = new vector[int]()
    for i in range(n):
        c = 0
        while 1:
            b = getchar() - 48
            if b < 0: break
            c = c * 10 + b
        v.push_back(c)
    return v[0]

cpdef inline vector[string] Read(int n):
    cdef char c
    cdef vector[string] *vs = new vector[string]()
    cdef string *s
    for i in range(n):
        s = new string()
        while 1:
            c = getchar()
            if c<=32: break
            s.push_back(c)
        vs.push_back(s[0])
    return vs[0]

cpdef inline void PrintLongN(vector[long] l, int n):
    for i in range(n): printf("%ld\\n", l[i])

cpdef inline void PrintLong(vector[long] l, int n):
    for i in range(n): printf("%ld ", l[i])
cdef extern from *:
    ctypedef long long ll "long long"

cdef extern from "<atcoder/mincostflow>" namespace "atcoder":
    cdef cppclass mcf_graph[Cap, Cost]:
        mcf_graph(int n)
        int add_edge(int fr, int to, Cap cap, Cost cost)
        pair[Cap, Cost] flow(int s, int t)
        pair[Cap, Cost] flow(int s, int t, Cap flow_limit)
        vector[pair[Cap, Cost]] slope(int s, int t)
        vector[pair[Cap, Cost]] slope(int s, int t, Cap flow_limit)
        cppclass edge:
            int frm 'from'
            int to
            Cap cap
            Cap flow
            Cost cost
            edge(edge &e)
        edge get_edge(int i)
        vector[edge] edges()

cdef class McfGraph:
    cdef mcf_graph[int, ll] *_thisptr
    def __cinit__(self, int n):
        self._thisptr = new mcf_graph[int, ll](n)
    cpdef int add_edge(self, int fr, int to, int cap, ll cost):
        return self._thisptr.add_edge(fr, to, cap, cost)
    cpdef pair[int, ll] flow(self, int s, int t):
        return self._thisptr.flow(s, t)
    cpdef pair[int, ll] flow_with_limit(self, int s, int t, int flow_limit):
        return self._thisptr.flow(s, t, flow_limit)
    cpdef vector[pair[int, ll]] slope(self, int s, int t):
        return self._thisptr.slope(s, t)
    cpdef vector[pair[int, ll]] slope_with_limit(self, int s, int t, int flow_limit):
        return self._thisptr.slope(s, t, flow_limit)

    cpdef pair[vector[int], ll] get_edge(self, int i):
        cdef mcf_graph[int, ll].edge *e = new mcf_graph[int, ll].edge(self._thisptr.get_edge(i))
        cdef pair[vector[int], ll] *ret_e = new pair[vector[int], ll]()
        ret_e.first.push_back(e.frm)
        ret_e.first.push_back(e.to)
        ret_e.first.push_back(e.cap)
        ret_e.first.push_back(e.flow)
        ret_e.second = e.cost
        return ret_e[0]

    cpdef vector[pair[vector[int], ll]] edges(self):
        cdef vector[mcf_graph[int, ll].edge] es = self._thisptr.edges()
        cdef vector[pair[vector[int], ll]] *ret_es = new vector[pair[vector[int], ll]](es.size())
        for i in range(es.size()):
            ret_es.at(i).first.push_back(es.at(i).frm)
            ret_es.at(i).first.push_back(es.at(i).to)
            ret_es.at(i).first.push_back(es.at(i).cap)
            ret_es.at(i).first.push_back(es.at(i).flow)
            ret_es.at(i).second = es.at(i).cost
        return ret_es[0]
"""


import os, sys, getpass

if sys.argv[-1] == 'ONLINE_JUDGE':
    code = code.replace("USERNAME", getpass.getuser())
    open('intermediate.hpp','w').write(header_code)
    open('atcoder.pyx','w').write(code)
    os.system('cythonize -i -3 -b atcoder.pyx')
    sys.exit(0)


from atcoder import McfGraph, ReadInt, PrintLongN

def main():
    n, k = ReadInt(2)
    mg = McfGraph(2*n+2)
    s = 2 * n
    t = 2 * n + 1
    BIG = 1000000000

    mg.add_edge(s, t, n * k, BIG);

    for i in range(n):
        mg.add_edge(s, i, k, 0)
        mg.add_edge(n + i, t, k, 0)


    for i in range(n):
        for j in range(n):
            mg.add_edge(i, n + j, 1, BIG - ReadInt(1)[0])

    result = mg.flow_with_limit(s, t, n * k)
    print(n * k * BIG - result[1])
    S = [["."]*n for i in range(n)]
    edges = mg.edges()
    for e in edges:
        if e[0][0] == s or e[0][1] == t or e[0][3] == 0:
            continue
        S[e[0][0]][e[0][1] - n] = 'X'

    print(*["".join(s) for s in S], sep="\n")

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import heapq

class mcf_graph_int_cost:
    """
    頂点数、及び、costの総和が、4294967295 (== (1 << 32) - 1) を超えない前提下での高速な実装。
    後者は超えても一応動く。
    """

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


    def add_edge(self, from_, to, cap, cost):
        # assert 0 <= from_ < self.n
        # assert 0 <= to < self.n
        m = len(self.pos)
        self.pos.append((from_, len(self.g[from_])))
        self.g[from_].append(self.__class__._edge(to, len(self.g[to]), cap, cost))
        self.g[to].append(self.__class__._edge(from_, len(self.g[from_]) - 1, 0, -cost))
        return m


    class edge:
        def __init__(self, from_, to, cap, flow, cost):
            self.from_ = from_
            self.to = to
            self.cap = cap
            self.flow = flow
            self.cost = cost


    def get_edge(self, i):
        _e = self.g[self.pos[i][0]][self.pos[i][1]]
        _re = self.g[_e.to][_e.rev]
        return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)


    def edges(self):
        ret = []
        for i in range(len(self.pos)):
            _e = self.g[self.pos[i][0]][self.pos[i][1]]
            _re = self.g[_e.to][_e.rev]
            ret.append(self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost))
        return ret


    def _dual_ref(self):
        self.dist = [4294967295] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n

        que = [s]
        self.dist[s] = 0
        while que:
            v = heapq.heappop(que) & 4294967295
            if self.vis[v]:
                continue
            self.vis[v] = True
            if v == t:
                break
            for i in range(len(self.g[v])):
                e = self.g[v][i]
                if self.vis[e.to] or e.cap == 0:
                    continue
                cost = e.cost - self.dual[e.to] + self.dual[v]
                if self.dist[e.to] > self.dist[v] + cost:
                    self.dist[e.to] = self.dist[v] + cost
                    self.pv[e.to] = v
                    self.pe[e.to] = i
                    assert ((self.dist[e.to] << 32) + e.to) < 2 ** 64 # 興味本位
                    heapq.heappush(que, ((self.dist[e.to] << 32) + e.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


    def slope(self, s, t, flow_limit=4294967295):
        # assert 0 <= s < self.n
        # assert 0 <= t < self.n
        # assert s != t
        
        self.dual = [0] * self.n
        self.dist = [4294967295] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n
        
        flow = 0
        cost = 0
        prev_cost = -1
        result = [(flow, cost)]
        while flow < flow_limit:
            if not self._dual_ref():
                break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
                v = self.pv[v]
            v = t
            while v != s:
                e = self.g[self.pv[v]][self.pe[v]]
                e.cap -= c
                self.g[v][e.rev].cap += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result.pop()
            result.append((flow, cost))
            prev_cost = cost
        return result


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

    
    class _edge:
        def __init__(self, to, rev, cap, cost):
            self.to = to
            self.rev = rev
            self.cap = cap
            self.cost = cost


BIG = 10 ** 9

import sys
input = sys.stdin.readline

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

g = mcf_graph_int_cost(2 * N + 2)
s = 2 * N
t = 2 * N + 1

g.add_edge(s, t, N * K, BIG)
for i in range(N):
    g.add_edge(s, i, K, 0)
    g.add_edge(N + i, t, K, 0)

for i in range(N):
    As = map(int, input().split())
    for j, A in enumerate(As):
        g.add_edge(i, N + j, 1, BIG - A)

result = g.flow(s, t, N * K)

print(N * K * BIG - result[1])

grid = [['.' for _ in range(N)] for _ in range(N)]
edges = g.edges()
for e in edges:
    if e.from_ == s or e.to == t or e.flow == 0:
        continue
    grid[e.from_][e.to - N] = 'X'

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

Submission status: Accepted

Solution code:
import heapq

class mcf_graph_int_cost:
    """
    頂点数、及び、costの総和が、4294967295 (== (1 << 32) - 1) を超えない前提下での高速な実装。
    後者は超えても一応動く。
    """

    __slots__ = ["n", "pos", "g", "dual", "dist", "pv", "pe", "vis"]

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


    def add_edge(self, from_, to, cap, cost):
        # assert 0 <= from_ < self.n
        # assert 0 <= to < self.n
        m = len(self.pos)
        self.pos.append((from_, len(self.g[from_])))
        self.g[from_].append(self.__class__._edge(to, len(self.g[to]), cap, cost))
        self.g[to].append(self.__class__._edge(from_, len(self.g[from_]) - 1, 0, -cost))
        return m


    class edge:
        def __init__(self, from_, to, cap, flow, cost):
            self.from_ = from_
            self.to = to
            self.cap = cap
            self.flow = flow
            self.cost = cost


    def get_edge(self, i):
        _e = self.g[self.pos[i][0]][self.pos[i][1]]
        _re = self.g[_e.to][_e.rev]
        return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)


    def edges(self):
        ret = []
        for i in range(len(self.pos)):
            _e = self.g[self.pos[i][0]][self.pos[i][1]]
            _re = self.g[_e.to][_e.rev]
            ret.append(self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost))
        return ret


    def _dual_ref(self):
        self.dist = [4294967295] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n

        que = [s]
        self.dist[s] = 0
        while que:
            v = heapq.heappop(que) & 4294967295
            if self.vis[v]:
                continue
            self.vis[v] = True
            if v == t:
                break
            for i in range(len(self.g[v])):
                e = self.g[v][i]
                if self.vis[e.to] or e.cap == 0:
                    continue
                cost = e.cost - self.dual[e.to] + self.dual[v]
                if self.dist[e.to] > self.dist[v] + cost:
                    self.dist[e.to] = self.dist[v] + cost
                    self.pv[e.to] = v
                    self.pe[e.to] = i
                    heapq.heappush(que, ((self.dist[e.to] << 32) + e.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


    def slope(self, s, t, flow_limit=4294967295):
        # assert 0 <= s < self.n
        # assert 0 <= t < self.n
        # assert s != t
        
        self.dual = [0] * self.n
        self.dist = [4294967295] * self.n
        self.pv = [-1] * self.n
        self.pe = [-1] * self.n
        self.vis = [False] * self.n
        
        flow = 0
        cost = 0
        prev_cost = -1
        result = [(flow, cost)]
        while flow < flow_limit:
            if not self._dual_ref():
                break
            c = flow_limit - flow
            v = t
            while v != s:
                c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
                v = self.pv[v]
            v = t
            while v != s:
                e = self.g[self.pv[v]][self.pe[v]]
                e.cap -= c
                self.g[v][e.rev].cap += c
                v = self.pv[v]
            d = -self.dual[s]
            flow += c
            cost += c * d
            if prev_cost == d:
                result.pop()
            result.append((flow, cost))
            prev_cost = cost
        return result


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

    
    class _edge:
        def __init__(self, to, rev, cap, cost):
            self.to = to
            self.rev = rev
            self.cap = cap
            self.cost = cost


BIG = 10 ** 9

import sys
input = sys.stdin.readline

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

g = mcf_graph_int_cost(2 * N + 2)
s = 2 * N
t = 2 * N + 1

g.add_edge(s, t, N * K, BIG)
for i in range(N):
    g.add_edge(s, i, K, 0)
    g.add_edge(N + i, t, K, 0)

for i in range(N):
    As = map(int, input().split())
    for j, A in enumerate(As):
        g.add_edge(i, N + j, 1, BIG - A)

result = g.flow(s, t, N * K)

print(N * K * BIG - result[1])

grid = [['.' for _ in range(N)] for _ in range(N)]
edges = g.edges()
for e in edges:
    if e.from_ == s or e.to == t or e.flow == 0:
        continue
    grid[e.from_][e.to - N] = 'X'

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