Problem:


Score : 600 points

Problem Statement

There is a board with N rows and M columns.
The information of this board is represented by N strings S_1,S_2,\ldots,S_N.
Specifically, the state of the square at the i-th row from the top and the j-th column from the left is represented as follows:

S_{i,j}=. : the square is empty.

S_{i,j}=# : an obstacle is placed on the square.

S_{i,j}=o : a piece is placed on the square.

Yosupo repeats the following operation:

Choose a piece and move it to its right adjecent square or its down adjacent square.
Moving a piece to squares with another piece or an obstacle is prohibited.
Moving a piece out of the board is also prohibited.

Yosupo wants to perform the operation as many times as possible.
Find the maximum possible number of operations.

Constraints

1 \leq N \leq 50

1 \leq M \leq 50

S_i is a string of length M consisting of ., # and o.

1 \leq ( the number of pieces )\leq 100.
In other words, the number of pairs (i, j) that satisfy S_{i,j}=o is between 1 and 100, both inclusive.

Input

Input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Print the maximum possible number of operations in a line.

Sample Input 1

3 3
o..
...
o.#

Sample Output 1

4

Yosupo can perform operations 4 times as follows:

o..      .o.      ..o      ...      ...
...  ->  ...  ->  ...  ->  ..o  ->  ..o
o.#      o.#      o.#      o.#      .o#

Sample Input 2

9 10
.#....o#..
.#..#..##o
.....#o.##
.###.#o..o
#.#...##.#
..#..#.###
#o.....#..
....###..o
o.......o#

Sample Output 2

24



Sample input:
3 3
o..
...
o.#


Sample output:
4

Submission status: Runtime Error

Solution code:
import types

_atcoder_code = """
# Python port of AtCoder Library.

__version__ = '0.0.1'
"""

atcoder = types.ModuleType('atcoder')
exec(_atcoder_code, atcoder.__dict__)

_atcoder_maxflow_code = """
from __future__ import annotations

from typing import NamedTuple, Optional, List


class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = e.rev
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = sum(e.cap for e in self._g[s])

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = e.rev
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited
"""

atcoder.maxflow = types.ModuleType('atcoder.maxflow')
exec(_atcoder_maxflow_code, atcoder.maxflow.__dict__)
MFGraph = atcoder.maxflow.MFGraph

# from atcoder.maxflow import MFGraph

n,m = map(int,input().split())
S = [input() for i in range(n)]
t = 100*(n+m) + 100
 

cap = 10**9


M = MFGraph(n*m*t + 2)
s = n*m*t
g = n*m*t+1
nm = n*m

for i in range(t-1):
    for j in range(n):
        for k in range(m):
            if S[j][k] != "#":
                if j+1 < n and S[j+1][k] != "#":
                    M.add_edge(i*nm+j*m+k, (i+1)*nm+(j+1)*m+k, cap)
                if k+1 < m and S[j][k+1] != "#":
                    M.add_edge(i*nm+j*m+k, (i+1)*nm+j*m+k+1, cap)

for i in range(1, t):
    for j in range(n):
        for k in range(m):
            if S[j][k] != "#":
                M.add_edge(i*nm+j*m+k, g, 1)
c=0
for j in range(n):
    for k in range(m):
        if S[j][k] == "o":
            c += 1
            M.add_edge(s, j*m+k, cap)

print(M.flow(s,g)-2*c)
# print(M.edges())

Submission status: Runtime Error

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

import numpy as np


def solve(n, m, field):
    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

    nm = (n + 2) * (m + 2)
    m2 = m + 2

    starts = np.where(field == 1)[0]
    s_size = starts.size

    ins = mincostflow_init(nm + s_size + 2)
    s = nm + s_size
    t = s + 1

    stack = np.zeros(10 ** 7, np.int64)

    for i in range(s_size):
        mincostflow_add_link(ins, s, nm + i, 1, 0)

        stack[0] = starts[i]
        stack[1] = 0
        sl = 0
        sr = 2
        stacked = np.zeros(nm, np.int8)
        stacked[starts[i]] = 1
        while sl < sr:
            v = stack[sl]
            c = stack[sl + 1]
            sl += 2

            mincostflow_add_link(ins, nm + i, v, 1, INF - c)

            if stacked[v + 1] == 0 and field[v + 1] != 2:
                stack[sr] = v + 1
                stack[sr + 1] = c + 1
                stacked[v + 1] = 1
                sr += 2
            if stacked[v + m2] == 0 and field[v + m2] != 2:
                stack[sr] = v + m2
                stack[sr + 1] = c + 1
                stacked[v + m2] = 1
                sr += 2

    for i in range(nm):
        if field[i] != 2:
            mincostflow_add_link(ins, i, t, 1, 0)

    mincostflow_fix_link(ins, nm + s_size + 2)
    f = mincostflow_flow(ins, s, t, s_size)

    ans = INF * s_size - f
    return ans


SIGNATURE = '(i8,i8,i1[:],)'
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, m = map(int, sys.stdin.readline().split())
field = '#' * (m + 3) + '##'.join(sys.stdin.read().split()) + '#' * (m + 3)
field = np.fromiter(map('.o#'.index, field), np.int8)
ans = solve(n, m, field)
print(ans)

Submission status: Runtime Error

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

import numpy as np


def solve(n, m, field):
    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

    nm = (n + 2) * (m + 2)
    m2 = m + 2

    starts = np.where(field == 1)[0]
    s_size = starts.size

    ins = mincostflow_init(nm + s_size + 2)
    s = nm + s_size
    t = s + 1

    stack = np.zeros(10 ** 7, np.int64)
    stacked = np.zeros(nm, np.int8)

    for i in range(s_size):
        mincostflow_add_link(ins, s, nm + i, 1, 0)

        stack[0] = starts[i]
        stack[1] = 0
        sl = 0
        sr = 2
        stacked.fill(0)
        stacked[starts[i]] = 1
        while sl < sr:
            v = stack[sl]
            c = stack[sl + 1]
            sl += 2

            mincostflow_add_link(ins, nm + i, v, 1, INF - c)

            if stacked[v + 1] == 0 and field[v + 1] != 2:
                stack[sr] = v + 1
                stack[sr + 1] = c + 1
                stacked[v + 1] = 1
                sr += 2
            if stacked[v + m2] == 0 and field[v + m2] != 2:
                stack[sr] = v + m2
                stack[sr + 1] = c + 1
                stacked[v + m2] = 1
                sr += 2

    for i in range(nm):
        if field[i] != 2:
            mincostflow_add_link(ins, i, t, 1, 0)

    mincostflow_fix_link(ins, nm + s_size + 2)
    f = mincostflow_flow(ins, s, t, starts.size)

    ans = INF * starts.size - f
    return ans


SIGNATURE = '(i8,i8,i1[:],)'
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, m = map(int, sys.stdin.readline().split())
field = '#' * (m + 3) + '##'.join(sys.stdin.read().split()) + '#' * (m + 3)
field = np.fromiter(map('.o#'.index, field), np.int8)
ans = solve(n, m, field)
print(ans)

Submission status: Runtime Error

Solution code:
import networkx as nx

n, m = map(int, input().split())

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, m)
cnt = 0
goal = (n, m + 1)

for i in range(n):
    for j in range(n):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < m:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(abs(ans))

Submission status: Runtime Error

Solution code:
import networkx as nx

n, m = map(int, input().split())

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, n)
cnt = 0
goal = (n, n + 1)

for i in range(n):
    for j in range(n):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < n:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(-ans)

Submission status: Runtime Error

Solution code:
import networkx as nx
import sys

input = sys.stdin.buffer.readline

n, m = map(int, input().split())

S = [list(input()) for _ in range(n)]
G = nx.DiGraph()

start = (n, n)
cnt = 0
goal = (n, n + 1)

for i in range(n):
    for j in range(n):
        if S[i][j] != "#":
            if S[i][j] == "o":
                cnt += 1
                G.add_edge(start, (i, j), capacity=1)
            if i + 1 < n:
                if S[i + 1][j] != "#":
                    G.add_edge((i, j), (i + 1, j), weight=-1)
            if j + 1 < n:
                if S[i][j + 1] != "#":
                    G.add_edge((i, j), (i, j + 1), weight=-1)
            G.add_edge((i, j), goal, capacity=1)
# G.add_node(start, demand=cnt)
# G.add_node(goal, demand=-cnt)
mincostflow = nx.max_flow_min_cost(G, start, goal)
ans = nx.cost_of_flow(G, mincostflow)
print(-ans)