Problem:


Score : 400 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.

Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.

Snuke wants to maximize the number of squares lighted by the lamp.

You are given H strings S_i (1 \leq i \leq H), each of length W. If the j-th character (1 \leq j \leq W) of S_i is #, there is an obstacle on the square at the i-th row from the top and the j-th column from the left; if that character is ., there is no obstacle on that square.

Find the maximum possible number of squares lighted by the lamp.

Constraints

1 \leq H \leq 2,000

1 \leq W \leq 2,000

S_i is a string of length W consisting of # and ..

. occurs at least once in one of the strings S_i (1 \leq i \leq H).

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the maximum possible number of squares lighted by the lamp.

Sample Input 1

4 6
#..#..
.....#
....#.
#.#...

Sample Output 1

8

If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.

Sample Input 2

8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#

Sample Output 2

13



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
s = []
for i in range(h):
  s.append(list(input()))
r1 = np.zeros((h, w))
for i in range(h):
  tmp = []
  for j in range(w):
    if s[i][j] == '#':
      r1[i][j] = 0
      if len(tmp) > 0:
        for k in tmp:
          r1[i][k] = len(tmp)
      tmp = []
    else:
      tmp.append(j)
  else:
    if len(tmp) > 0:
      for k in tmp:
        r1[i][k] = len(tmp)
r2 = np.zeros((h, w))
for j in range(w):
  tmp = []
  for i in range(h):
    if s[i][j] == '#':
      r2[i][j] = 0
      if len(tmp) > 0:
        for k in tmp:
          r2[k][j] = len(tmp)
      tmp = []
    else:
      tmp.append(i)
  else:
    if len(tmp) > 0:
      for k in tmp:
        r2[k][j] = len(tmp)
print(int(np.max(r1 + r2 - 1)))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = ['' for h in range(H)]
L = [[[0, 0] for w in range(W + 1)] for h in range(H + 1)]
for i in range(H):
  S[i] = input()
  l = 0
  for j in range(W):
    if S[i][j] == '#':
      L[i][j - l][0] = l
      L[i][j][0] = -l
      l = 0
    else:
      l += 1
  L[i][W - l][0] = l
  L[i][W][0] = -l
for j in range(W):
  u = 0
  for i in range(H):
    if S[i][j] == '#':
      L[i - u][j][1] = u
      L[i][j][1] = -u
      u = 0
    else:
      u += 1
  L[H - u][j][1] = u
  L[H][j][1] = -u
for i in range(H):
  for j in range(1, W):
    L[i][j][0] += L[i][j - 1][0]
for j in range(W):
  for i in range(1, H):
    L[i][j][1] += L[i - 1][j][1]
ans = 0
for i in range(H):
  for j in range(W):
    ans = max(sum(L[i][j]) - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = []
for i in range(H):
	S.append(list(input()))

area_yoko = []
area_tate = []

area_yoko_length = []
area_tate_length = []
for i in range(H):
	tmp = [-1000000 for j in range(W)]
	yoko = S[i]
	area_start = 0
	kabe = yoko[0] == "#"
	tmp_length = []
	idx = 0
	j = 0
	while j < W:
		if yoko[j] == ".":
			if kabe:
				kabe = False
				area_start = j
			tmp[j] = idx
			j += 1
			continue
		else:
			if not kabe:
				kabe = True
				tmp_length.append(j-area_start)
				idx += 1
			j += 1
			continue
	if not kabe:
		tmp_length.append(W-area_start)
	area_yoko.append(tmp)
	area_yoko_length.append(tmp_length)


for i in range(W):
	tmp = [-1000000 for j in range(H)]
	tmp_length = []
	tate = [S[j][i] for j in range(H)]
	area_start = 0
	kabe = tate[0] == "#"
	idx = 0
	j = 0
	while j < H:
		if tate[j] == ".":
			if kabe:
				kabe = False
				area_start = j
			tmp[j] = idx
			j += 1
			continue
		else:
			if not kabe:
				kabe = True
				tmp_length.append(j-area_start)
				idx += 1
			j += 1
			continue
	if not kabe:
		tmp.append((area_start, H-1, idx))
		tmp_length.append(H-area_start)

	area_tate.append(tmp)
	area_tate_length.append(tmp_length)

ans = 0
for y in range(H):
	for x in range(W):
		if S[y][x] != "#":
			ans = max(ans, area_yoko_length[y][area_yoko[y][x]] + area_tate_length[x][area_tate[x][y]] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = [[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)]
  v = numpy.zeros((r, c), dtype=numpy.int)

  for y in range(r):
    s = 0
    for x in range(c):
      if g[y][x] == 0:
        v[y, s:x] += x - s
        s = x + 1

    v[y, s:] += c - s

  for x in range(c):
    s = 0
    for y in range(r):
      if g[y][x] == 0:
        v[s:y, x] += y - s
        s = y + 1

    v[s:, x] += r - s

  print(numpy.max(v) - 1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())

room = [[True if c == "." else False for c in input()] for _ in range(H)]

count = []

for i in range(H):
    count.append([0] * W)


def check(row,col):
    px = col
    py = row
    while py >= 0:
        if not room[py][px]:
            break
        count[py][px] += 1
        py -= 1
    py = row + 1
    while py < H:
        if not room[py][px]:
            break
        count[py][px] += 1
        py += 1
    py = row

    while px >= 0:
        if not room[py][px]:
            break
        count[py][px] += 1
        px -= 1
    px = col + 1
    while px < W:
        if not room[py][px]:
            break
        count[py][px] += 1
        px += 1


for row in range(H):
    for col in range(W):
        if room[row][col]:
            check(row, col)

ans = 0

for rowline in count:
    ans = max(max(rowline), ans)

print((ans - 1))

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
S = [input() for _ in range(H)]


# 全要素でループ
ans = 0
for xi in range(W):
    for yi in range(H):
        
        #障害物がなかったらカウント開始
        if S[yi][xi] == '#':
            continue
        
        tmp = 1
        
        #左の.の数をカウント
        count = ''.join(list(reversed(S[yi][0:xi]))).find('#')
        if count == -1:
            tmp += ''.join(list(reversed(S[yi][0:xi]))).count('.')
        else:
            tmp += count
               
        #右の.の数をカウント
        count = S[yi][xi+1:].find('#')
                 
        if count == -1:
            tmp += S[yi][xi+1:].count('.')
        else:
            tmp += count
            
        #上の.の数をカウント
        row_str = ''.join(list(row[xi] for row in S))
        count = row_str[yi+1:].find('#')
                      
        if count == -1:
            tmp += row_str[yi+1:].count('.')
        else:
            tmp += count
         
        #下の.の数をカウント
        count = ''.join(list(reversed(row_str[0:yi]))).find('#')
        if count == -1:
            tmp += ''.join(list(reversed(row_str[0:yi]))).count('.')
        else:
            tmp += count

        ans = max(ans, tmp)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
S = []
for _ in range(h):
  s = list(input())
  S.append(s)

m = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == "#":
      continue
    cnt = 1
    for [x, y] in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      [a, b] = [i, j]
      while True:
        a += x
        b += y
        if a < 0 or a >= h or b < 0 or b >= w:
          break
        if S[a][b] == "#":
          break
        cnt += 1
    m = max(m, cnt)
print(m)

Submission status: Time Limit Exceeded

Solution code:
[h, w] = [int(i) for i in input().split()]
s = [input() for i in range(h)]

cnt = 0
r1 = []
for l in s:
    r1.append([])
    for c in l:
        if (c == '#'):
            r1[-1] += cnt * [cnt]
            cnt = 0
            r1[-1].append(0)
        else:
            cnt += 1
    r1[-1] += cnt * [cnt]
    cnt = 0

r2 = []
for i in range(w):
    r2.append([])
    for j in range(h):
        if (s[j][i] == '#'):
            r2[-1] += cnt * [cnt]
            cnt = 0
            r2[-1].append(0)
        else:
            cnt += 1
    r2[-1] += cnt * [cnt]
    cnt = 0

r3 = [[r1[i][j] + r2[j][i] - 1 for j in range(w)] for i in range(h)]
r4 = [max(l) for l in r3]
print(max(r4))

Submission status: Time Limit Exceeded

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

def f(H, W, S):
    hs = []
    vs = []
    sts = [0]*W

    for j, s in enumerate(S):
        st = 0
        
        for i, c in enumerate(s):
            if c == '#':
                if st < i:
                    hs.append((j, st, i))
                st = i+1

                if sts[i] < j:
                    vs.append((i, sts[i], j))

                sts[i] = j+1

        if st < W:
            hs.append((j, st, W))
            
    for i in range(W):
        if sts[i] < H:
            vs.append((i, sts[i], H))
        

    m = 0

    for h in hs:
        for v in vs:
            if h[0] >= v[1] and h[0] < v[2] and \
               v[0] >= h[1] and v[0] < h[2]:
    
                m = max(m,  h[2] - h[1] + v[2] - v[1] - 1)

    return m


def main():
    H,W = map(int, input().split())
    S = list(input() for i in range(H))
    print(f(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
L = []
for i in range(H):
	s = list(input())
	S.append(s)
	l = []
	count = 0
	for i in range(W):
		if s[i] == '#':
			for k in range(count):
				l.append(count)
			count = 0
			l.append(0)
		else:
			count += 1
	for k in range(count):
		l.append(count)
	L.append(l)
for i in range(W):
	count = 0
	for k in range(H):
		if L[k][i] == 0:
			for j in range(count):
				L[k - j - 1][i] += count
			count = 0
		else:
			count += 1
	for j in range(count):
		L[k - j - 1][i] += count			
ans = 0
for i in range(H):
	ans = max(max(L[i]) - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

H,W = inpl()

MAP = [list(input()) for y in range(H)]

yokoList = [[0]*W for y in range(H)]

for y in range(H):
    l = 0
    while l < W:
        if MAP[y][l] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= W or MAP[y][r] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for x in range(l,r):
                yokoList[y][x] = tmp
            l = r

tateList = [[0]*W for y in range(H)]

for x in range(W):
    l = 0
    while l < H:
        if MAP[l][x] == '#':
            l += 1
            continue
        else:
            r = l
            tmp = 0
            while True:
                if r >= H or MAP[r][x] == '#':
                    break
                else:
                    r += 1
                    tmp += 1
            for y in range(l,r):
                tateList[y][x] = tmp
            l = r



ans = 0
for y in range(H):
    for x in range(W):
        ans = max(tateList[y][x] + yokoList[y][x]-1, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())

yoko = [[0] * W for h in range(H)]
for row in range(H):
    count = 0
    for col in range(W):
        if grid[row][col] == '.':
            count += 1
            yoko[row][col] = count
        else:
            count = 0

    count = 0
    for col in range(W-1, -1, -1):
        if yoko[row][col] > 0:
            count = max(count, yoko[row][col])
            yoko[row][col] = count
        else:
            count = 0

tate = [[0] * W for h in range(H)]
for col in range(W):
    count = 0
    for row in range(H):
        if grid[row][col] == '.':
            count += 1
            tate[row][col] = count
        else:
            count = 0

    count = 0
    for row in range(H-1, -1, -1):
        if tate[row][col] > 0:
            count = max(count, tate[row][col])
            tate[row][col] = count
        else:
            count = 0

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, yoko[row][col] + tate[row][col] - 1)

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys


fin = sys.stdin.readline
H, W = [int(elem) for elem in fin().split()]
grid = [fin().rstrip("\n") for _ in range(H)]
assert len(grid[0]) == W

num_connected_rowwise = [[0] * W for _ in range(H)]
num_connected_colwise = [[0] * W for _ in range(H)]

for i, row in enumerate(grid):
    cur_n_connected = 0
    last_row = 0
    for j, cell in enumerate(row):
        if cell == ".":
            cur_n_connected += 1
        elif cell == '#':
            for k in range(last_row, j):
                num_connected_rowwise[i][k] = cur_n_connected
            cur_n_connected = 0
            last_row = j + 1
        for k in range(last_row, W):
            num_connected_rowwise[i][k] = cur_n_connected

for j in range(W):
    cur_n_connected = 0
    last_col = 0
    for i in range(H):
        cell = grid[i][j]
        if cell == ".":
            cur_n_connected += 1
        elif cell == "#":
            for k in range(last_col, i):
                num_connected_colwise[k][j] = cur_n_connected
            cur_n_connected = 0
            last_col = i + 1
        for k in range(last_col, H):
            num_connected_colwise[k][j] = cur_n_connected

max_num = 0
for i in range(H):
    for j in range(W):
        max_num = max(max_num, num_connected_colwise[i][j] + num_connected_rowwise[i][j] - 1)
# print(num_connected_rowwise)
# print(num_connected_colwise)
print(max_num)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
s = [input() for _ in range(h)]

rows = [[0 for _ in range(w)] for _ in range(h)]
cols = [[0 for _ in range(h)] for _ in range(w)]

field = [[0 for _ in range(w)] for _ in range(h)]

temp = [[len(v) for v in row.split("#")] for row in s]

for i in range(h):
  index = 0
  for j in range(w):
    if s[i][j] == "#":
      index += 1
    else:
      rows[i][j] = temp[i][index]

s_t = list(zip(*s))
s_t = ["".join(v) for v in s_t]

temp = [[len(v) for v in str(row).split("#")] for row in s_t]

for i in range(w):
  index = 0
  for j in range(h):
    if s[j][i] == "#":
      index += 1
    else:
      cols[i][j] = temp[i][index]

cols = list(zip(*cols))

for i in range(h):
  for j in range(w):
    field[i][j] = rows[i][j] + cols[i][j] -1

print(max([max(v) for v in field]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    h, w = map(int, input().split())
    grid = [input() for _ in range(h)]
    field = np.array([[0] * w for _ in range(h)])

    for i, row in enumerate(grid):
        row = row + "#"
        cnt = row.count("#")

        idx = -1
        for j in range(cnt + 1):
            idx_next = row.find("#", idx + 1)
            field[i][idx+1:idx_next] = idx_next - idx - 1
            idx = idx_next

    m = 0
    field = field.T

    for i, row in enumerate(zip(*grid)):
        row = "".join(row) + "#"
        cnt = row.count("#")

        idx = -1
        for j in range(cnt + 1):
            idx_next = row.find("#", idx + 1)
            field[i][idx+1:idx_next] += idx_next - idx - 1
            idx = idx_next
        if max(field[i]) > m:
            m = max(field[i])

    print(m - 1)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split(" "))

S = np.asarray([list(input()) for i in range(H)])
#print("S", S)

map_yoko = np.zeros((H, W), dtype=int)
map_tate = np.zeros((H, W), dtype=int)

# yoko
for i in range(H):
    count = 0
    kabe = True
    start = None
    end = None
    for j in range(W):
        if S[i][j] == "#":
            end = j-1
            kabe = True
            
            #print(i, j, start, end, count)
            #if start is not None:
            if count >= 1:
                map_yoko[i, start:end+1] = count
            count = 0

        else:
            count += 1
            if kabe:
                kabe = False
                start = j

            if j == W-1:
                end = j
                map_yoko[i, start:end+1] = count


# tate
for j in range(W):
    count = 0
    kabe = True
    start = None
    end = None
    for i in range(H):
        if S[i][j] == "#":
            end = i-1
            kabe = True
            
            if count >= 1:
                map_tate[start:end+1, j] = count
            count = 0

        else:
            count += 1
            if kabe:
                kabe = False
                start = i

            if i == H-1:
                end = i
                map_tate[start:end+1, j] = count

#print("yoko\n", map_yoko)
#print("tate\n", map_tate)


map_ = map_yoko + map_tate
out = map_.max() - 1

print(out)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def f(line):
    res = np.zeros_like(line, dtype=np.int)
    acc = 0
    for i, v in enumerate(line):
        if v == "#":
            res[i] = 0
            acc = 0
        else:
            acc += 1
            res[i] = acc

    prev = 0
    for i in reversed(range(len(res))):
        if res[i] == 0:
            prev = 0
        else:
            res[i] = max(prev, res[i])
            prev = res[i]

    return res


H, W = map(int, input().split())
grid = np.array([list(input().strip()) for _ in range(H)])

row_wise = np.array([f(np.array(row)) for row in grid])
col_wise = np.array([f(np.array(col)) for col in grid.T]).T

# print(row_wise)
# print(col_wise)
# print(row_wise + col_wise - 1)

print((row_wise + col_wise - 1).max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main(H, W, s_list):
    row_count = np.zeros((H, W))
    for i_row in range(H):
        i_col = 0
        j_col = 0
        s = s_list[i_row]
        while(i_col < W):
            char = s[i_col]
            j_col = i_col
            
            if char == '.':
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s[j_col]
                    if c == '#':
                        break

                row_count[i_row, i_col:j_col] = j_col - i_col
            i_col = j_col + 1


    col_count = np.zeros((H, W))
    for i_col in range(W):
        i_row = 0
        j_row = 0
        s_col = [s[i_col] for s in s_list]
        while(i_row < H):
            char = s_col[i_row]
            j_row = i_row
            if char == '.':
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_col[j_row]
                    if c == '#':
                        break
                
                col_count[i_row:j_row, i_col] = j_row - i_row
            i_row = j_row + 1
    print(int(np.max(row_count + col_count)) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def main():
    H, W = LI()
    S = [0 for _ in range(H)]
    for i in range(H):
        str = input()
        for j, s in enumerate(str):
            if s == '#':
                S[i] |= 1 << j
    ans = 1
    now = 1
    for i in range(H):
        for j in range(W):
            now = 1
            if (S[i] >> j) & 1:
                continue
            for k in range(j+1, W):
                if (S[i] >> k) & 1:
                    break
                now += 1
            for k in range(j-1, -1, -1):
                if (S[i] >> k) & 1:
                    break
                now += 1
            for k in range(i+1, H):
                if (S[k] >> j) & 1:
                    break
                now += 1
            for k in range(i-1, -1, -1):
                if (S[k] >> j) & 1:
                    break
                now += 1
            ans = max(ans, now)
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
S = []
for i in range(h):
    S.append(input())

sw = []

for i in range(h):
    c = []
    for j in range(w):
        if S[i][j] == '#':
            c.append(j)
    c.append(w)
    k = []
    p = c[0]
    k += [p] * p
    k += [0]
    for j in range(1, len(c)):
        p = c[j] - c[j-1] - 1
        k += [p] * p
        k += [0]
    sw.append(k)

sh =[]

for i in range(w):
    c = []
    for j in range(h):
        if S[j][i] == '#':
            c.append(j)
    c.append(h)
    k = []
    p = c[0]
    k += [p] * p
    k += [0]
    for j in range(1, len(c)):
        p = c[j] - c[j-1] - 1
        k += [p] * p
        k += [0]
    sh.append(k)

sw = np.array(sw)
sh = np.array(sh)
sh = sh.T

x = []

for i in range(h):
    for j in range(w):
        if sw[i][j] + sh[i][j]:
            x.append(sw[i][j] + sh[i][j]-1)

print(max(x))

Submission status: Time Limit Exceeded

Solution code:
import collections as c
ip = lambda : map(int, input().split())
# ##############
mod = 1e9+7
H,W = ip()
g = ['#'*(W+2)]
for i in range(H):
    g.append('#' + input() + '#')
g.append('#'*(W+2))
ans = [[0]*(W+2) for _ in range(H+2)]
submit = 0

# for i in g:
#     print(i)
for i in range(1,H+2):
    tmp = g[i]
    n = 0
    for j in range(1,W+2):
        if tmp[j] == '#':
            if j - n ==1:
                pass
            else:
                ans[i][n+1:j] = [j-n-1]*(j-n-1)
            n = j
# for i in ans:
#     print(i)
# print('#######')

for i in range(1,W+2):
    n=0
    for j in range(1,H+2):
        if g[j][i] == '#':
            if j - n ==1:
                pass
            else:
                for k in range(n+1,j):
                    ans[k][i] += j-n-1
                    submit = max(submit,ans[k][i])
            n = j

# for i in ans:
#     print(i)
print(submit-1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(3000)

H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[-1] * (W+2) for i in range(H+2)]
lst_shita = [[-1] * (W+2) for i in range(H+2)]
lst_migi = [[-1] * (W+2) for i in range(H+2)]
lst_hidari = [[-1] * (W+2) for i in range(H+2)]

# print (lst_ue)
def ue(i, j):
    if lst_ue[i][j] != -1:
        return lst_ue[i][j]
    if lst[i][j] == '#':
        lst_ue[i][j] = 0
        return 0
    else:
        lst_ue[i][j] = ue(i-1, j) + 1
        return lst_ue[i][j]


def shita(i, j):
    if lst_shita[i][j] != -1:
        return lst_shita[i][j]
    if lst[i][j] == '#':
        lst_shita[i][j] = 0
        return 0
    else:
        lst_shita[i][j] = shita(i+1, j) + 1
        return lst_shita[i][j]        


def hidari(i, j):
    if lst_hidari[i][j] != -1:
        return lst_hidari[i][j]
    if lst[i][j] == '#':
        lst_hidari[i][j] = 0
        return 0
    else:
        lst_hidari[i][j] = hidari(i, j-1) + 1
        return lst_hidari[i][j]        

def migi(i, j):
    if lst_migi[i][j] != -1:
        return lst_migi[i][j]
    if lst[i][j] == '#':
        lst_migi[i][j] = 0
        return 0
    else:
        lst_migi[i][j] = migi(i, j+1) + 1
        return lst_migi[i][j]        

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if lst[i][j] != '#':
            ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
x = [list(input()) for _ in range(h)]
xh = [[0 for j in range(w)] for i in range(h)]
xw = [[0 for j in range(w)] for i in range(h)]
for j in range(w):
    u = 0
    for i in range(h):
        if x[i][j] == '#':
            for k in range(u, i):
                xh[k][j] = i - u
            u = i + 1
    for k in range(u, h):
        xh[k][j] = h - u

ans = 0
for i in range(h):
    l = 0
    tmp = []
    for j in range(w):
        if x[i][j] == '#':
            if len(tmp) > 0:
                ans = max(ans, max(tmp) + j - l - 1)
            l = j + 1
            tmp = []
        else:
            tmp.append(xh[i][j])
    if len(tmp) > 0:
        ans = max(ans, max(tmp) + w - l - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = [[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)]
  v = numpy.zeros((2, r, c), dtype=numpy.int)

  for y in range(r):
    s = 0
    for x in range(c):
      if g[y][x] == 0:
        v[0, y, s:x] = x - s
        s = x + 1

    v[0, y, s:] = c - s

  for x in range(c):
    s = 0
    for y in range(r):
      if g[y][x] == 0:
        v[1, s:y, x] = y - s
        s = y + 1

    v[1, s:, x] = r - s

  v = v[0] + v[1]

  print(numpy.max(v) - 1)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
words = lambda t : list(map(t, input().split()))

h,w = words(int)

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print("k:", k)
        for x in range(j,j+k):
            vplus = 0
            for vi in range(i-1,-1,-1):
                if grid[vi][x] == '#':
                    break
                else:
                    vplus += 1
            for vi in range(i+1,h):
                if grid[vi][x] == '#':
                    break
                else:
                    vplus += 1
            ans = max(ans, vplus+k)
        j = j+k
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, itertools
H,W = map(int, input().strip().split(' '))
room = [[-1 if i == '#' else 0 for i in line.strip()]+[-1] for line in sys.stdin]
room += [[-1]*(W+1)]

for h in range(H):
  l = 0
  for r in range(W+1):
    if room[h][r] == -1:
      for i in range(l,r): room[h][i] += r-l
      l = r+1
for w in range(W):
  l = 0
  for r in range(H+1):
    if room[r][w] == -1:
      for i in range(l,r): room[i][w] += r-l
      l = r+1
#print(room)
print(max(max(r) for r in room)-1)

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

H,W = map(int,input().split())
S = [[] for i in range(H)]
for i in range(H):
    S[i] = list(str(input()))

lights = [[(0,0) for j in range(W)] for i in range(H)]


def count_ver(i,j):
    cnt = 0
    for x in range(i,W):
        if S[j][x] == ".":
            cnt += 1
        else:
            break
    for x in range(i,W):
        if S[j][x] == ".":
            ver,hor = lights[j][x]
            lights[j][x] = (cnt,hor)
        else:
            break
    return cnt


def count_hor(i,j):
    cnt = 0
    for y in range(j,H):
        if S[y][i] == ".":
            cnt += 1
        else:
            break
    for y in range(j,H):
        if S[y][i] == ".":
            ver,hor = lights[y][i]
            lights[y][i] = (ver,cnt)
        else:
            break
    return cnt

ans = -1
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ver,hor = lights[i][j]
            if ver == 0:
                ver = count_ver(j,i)
                # print("ver",ver)
            if hor == 0:
                hor = count_hor(j,i)
                # print("hor",hor)
            ans = max(ans,hor+ver-1)
        # print("y,x:",i,j)
        # print("ver,hor",ver,hor)

# print(lights)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int,input().split())
G = [input() for k in range(H)]

def keisan(h,w):
    k = 0
    while h-k>=0:
        if G[h-k][w] == ".":
            k += 1
        else:
            break
    l = 0
    while h+l<H:
        if G[h+l][w] == ".":
            l += 1
        else:
            break
    m = 0
    while w-m>=0:
        if G[h][w-m] == ".":
            m += 1
        else:
            break
    n = 0
    while w+n < W:
        if G[h][w+n] == ".":
            n += 1
        else:
            break
    return k+l+m+n-3

ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
                ans = max(ans,keisan(h,w))
                if ans == H+W-1:
                    print(ans)
                    exit(0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
ri = lambda: int(input())
#rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rl = lambda: map(int,input().split())
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7

H,W=rl()
S=[]
for i in range(H):
    S.append(input())
M = [[0 for w in range(W)] for h in range(H)]
wM = [[0 for w in range(W)] for h in range(H)]
hM = [[0 for w in range(W)] for h in range(H)]

for h in range(H):
    cnt = 0
    for w in range(W):
        if S[h][w] == '#':
            M[h][w] = 1
            wM[h][w-1] = cnt
            cnt = 0
        else:
            wM[h][w] = -1
            cnt += 1
    if cnt != 0:
        wM[h][W-1] = cnt

for h in range(H):
    cnt = 0
    for w in range(W-1,-1,-1):
        if wM[h][w] > 0:
            cnt = wM[h][w]
        elif wM[h][w] == -1:
            wM[h][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H):
        if M[h][w] == 1:
            hM[h-1][w] = cnt 
            cnt = 0
        else:
            hM[h][w] = -1
            cnt += 1
    if cnt != 0:
        hM[H-1][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H-1,-1,-1):
        if hM[h][w] > 0:
            cnt = hM[h][w]
        elif hM[h][w] == -1:
            hM[h][w] = cnt

ans = 0
for h in range(H):
    for w in range(W):
        ret = wM[h][w] + hM[h][w]
        if wM[h][w] != 0 and hM[h][w] != 0:
            ret -= 1
        ans = max(ans,ret)
print(ans)