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:
H,W=map(int,input().split())
S = []
for _ in range(H):
  S.append(list(input()))
  
Left = [[0] * W for i in range(H)]
for i in range(H):
  cur=0
  for j in range(W):
    #cur=0
    if S[i][j]=='#':
      cur=0
    else:
      cur=cur+1
    Left[i][j]=cur
    
Right=[[0] * W for i in range(H)]
for i in range(H):
  cur=0
  for j in range(W-1,-1,-1):
    if S[i][j]=='#':
      cur=0
    else:
      cur+=1
      Right[i][j]=cur
      
Up=[[0] * W for i in range(H)]
for j in range(W):
  cur=0
  for i in range(H):
    if S[i][j]=='#':
      cur=0
    else:
      cur+=1
      Up[i][j]=cur
      
Down=[[0] * W for i in range(H)]
for j in range(W):
  cur=0
  for i in range(H-1,-1,-1):
    if S[i][j]=='#':
      cur=0
    else:
      cur+=1
      Down[i][j]=cur
      
res=0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    res=max(res,Left[i][j]+Right[i][j]+Up[i][j]+Down[i][j]-3)
print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np

H, W = list(map(int, input().split()))
s_table = []
total_table = []
c_table = []
for _ in range(H):
    s = list(input())
    s_table.append(s)

c_table = np.zeros((H, W, 4))
total_table = np.zeros((H, W))

for i in range(H):
    for j in range(W):
        if j != 0:
            # 左側の数を数える
            if s_table[i][j - 1] == "." and s_table[i][j] == ".":
                c_table[i][j][0] = c_table[i][j - 1][0] + 1
                total_table[i][j] += c_table[i][j][0]
        if j != 0:
            # 右側の数を数える
            if s_table[i][W - j] == "." and s_table[i][W - j - 1] == ".":
                c_table[i][W - j - 1][1] = c_table[i][W - j][1] + 1
                total_table[i][W - j - 1] += c_table[i][W - j - 1][1]
        if i != 0:
            # 上側の数を数える
            if s_table[i - 1][j] == "." and s_table[i][j] == ".":
                c_table[i][j][2] = c_table[i - 1][j][2] + 1
                total_table[i][j] += c_table[i][j][2]
        if i != 0:
            # 下側の数を数える
            if s_table[H - i][j] == "." and s_table[H - i - 1][j] == ".":
                c_table[H - i - 1][j][3] = c_table[H - i][j][3] + 1
                total_table[H - i - 1][j] += c_table[H - i - 1][j][3]
# max_count = 0
# for i in range(H):
#     for j in range(W):
#         max_count = max(max_count, total_table[i][j])
ans = np.max(total_table) + 1
ans = int(ans)

# max_count = max([max(total_table[i]) for i in range(H)])
# ans = max_count + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# import numpy as np

H, W = list(map(int, input().split()))
s_table = []
total_table = []
c_table = []
for _ in range(H):
    s = list(input())
    s_table.append(s)
    total_table.append([0] * W)
    c_table.append([[0] * 4 for _ in range(W)])

for i in range(H):
    for j in range(W):
        if j != 0:
            # 左側の数を数える
            if s_table[i][j - 1] == "." and s_table[i][j] == ".":
                c_table[i][j][0] = c_table[i][j - 1][0] + 1
                total_table[i][j] += c_table[i][j][0]
        if j != 0:
            # 右側の数を数える
            if s_table[i][W - j] == "." and s_table[i][W - j - 1] == ".":
                c_table[i][W - j - 1][1] = c_table[i][W - j][1] + 1
                total_table[i][W - j - 1] += c_table[i][W - j - 1][1]
        if i != 0:
            # 上側の数を数える
            if s_table[i - 1][j] == "." and s_table[i][j] == ".":
                c_table[i][j][2] = c_table[i - 1][j][2] + 1
                total_table[i][j] += c_table[i][j][2]
        if i != 0:
            # 下側の数を数える
            if s_table[H - i][j] == "." and s_table[H - i - 1][j] == ".":
                c_table[H - i - 1][j][3] = c_table[H - i][j][3] + 1
                total_table[H - i - 1][j] += c_table[H - i - 1][j][3]
# max_count = 0
# for i in range(H):
#     for j in range(W):
#         max_count = max(max_count, total_table[i][j])
# ans = np.array(total_table).max() + 1
max_count = max([max(total_table[i]) for i in range(H)])
ans = max_count + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# import numpy as np

H, W = list(map(int, input().split()))
s_table = []
total_table = []
c_table = []
for _ in range(H):
    s = list(input())
    s_table.append(s)
    total_table.append([0] * W)
    c_table.append([[0] * 4 for _ in range(W)])

for i in range(H):
    for j in range(W):
        if j != 0:
            # 左側の数を数える
            if s_table[i][j - 1] == "." and s_table[i][j] == ".":
                c_table[i][j][0] = c_table[i][j - 1][0] + 1
                total_table[i][j] += c_table[i][j][0]
        if j != 0:
            # 右側の数を数える
            if s_table[i][W - j] == "." and s_table[i][W - j - 1] == ".":
                c_table[i][W - j - 1][1] = c_table[i][W - j][1] + 1
                total_table[i][W - j - 1] += c_table[i][W - j - 1][1]
        if i != 0:
            # 上側の数を数える
            if s_table[i - 1][j] == "." and s_table[i][j] == ".":
                c_table[i][j][2] = c_table[i - 1][j][2] + 1
                total_table[i][j] += c_table[i][j][2]
        if i != 0:
            # 下側の数を数える
            if s_table[H - i][j] == "." and s_table[H - i - 1][j] == ".":
                c_table[H - i - 1][j][3] = c_table[H - i][j][3] + 1
                total_table[H - i - 1][j] += c_table[H - i - 1][j][3]
max_count = 0
for i in range(H):
    for j in range(W):
        max_count = max(max_count, total_table[i][j])
# ans = np.array(total_table).max() + 1
ans = max_count + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import numpy as np

H, W = list(map(int, input().split()))
s_table = []
total_table = []
c_table = []
for _ in range(H):
    s = list(input())
    s_table.append(s)
    total_table.append([0] * W)
    c_table.append([[0] * 4 for _ in range(W)])

for i in range(H):
    for j in range(W):
        if j != 0:
            # 左側の数を数える
            if s_table[i][j - 1] == "." and s_table[i][j] == ".":
                c_table[i][j][0] = c_table[i][j - 1][0] + 1
                total_table[i][j] += c_table[i][j][0]
        if j != 0:
            # 右側の数を数える
            if s_table[i][W - j] == "." and s_table[i][W - j - 1] == ".":
                c_table[i][W - j - 1][1] = c_table[i][W - j][1] + 1
                total_table[i][W - j - 1] += c_table[i][W - j - 1][1]
        if i != 0:
            # 上側の数を数える
            if s_table[i - 1][j] == "." and s_table[i][j] == ".":
                c_table[i][j][2] = c_table[i - 1][j][2] + 1
                total_table[i][j] += c_table[i][j][2]
        if i != 0:
            # 下側の数を数える
            if s_table[H - i][j] == "." and s_table[H - i - 1][j] == ".":
                c_table[H - i - 1][j][3] = c_table[H - i][j][3] + 1
                total_table[H - i - 1][j] += c_table[H - i - 1][j][3]
ans = np.array(total_table).max() + 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    H, W = MAP()
    S = [input() for i in range(H)]
    # 上下左右
    L = [[0] * W for i in range(H)]
    R = [[0] * W for i in range(H)]
    D = [[0] * W for i in range(H)]
    U = [[0] * W for i in range(H)]
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                L[i][j] = 0
            elif j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            
    for i in range(H):
        for j in range(W-1, -1, -1):
            if S[i][j] == "#":
                R[i][j] = 0
            elif j == W-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                U[i][j] = 0
            elif i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

    for i in range(H-1, -1, -1):
        for j in range(W):
            if S[i][j] == "#":
                D[i][j] = 0
            elif i == H-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
  grid += '#' + input() + '#'
grid += '#' * (W+2)

move_list = [1, -1, W+2, -W-2]


def lamp(i):
  sum_ii_cnt = 1
  for move in move_list:
    ii = i
    while True:
      ii += move
      if grid[ii] == '#':
        break
      sum_ii_cnt += 1
  return sum_ii_cnt

'''ans = 0
for i in range((H+2)*(W+2)):
  if grid[i] != '#':
    ans = max(ans, lamp(i))'''

ans = max([ lamp(i) for i in range((H+2)*(W+2)) if grid[i] != '#' ])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]

left = [[0]*W for i in range(H)]
right = [[0]*W for i in range(H)]
up = [[0]*W for i in range(H)]
down = [[0]*W for i in range(H)]

for i in range(H):
    p = 0
    for j in range(W):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        left[i][j] = p
for i in range(H):
    p = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        right[i][j] = p
for j in range(W):
    p = 0
    for i in range(H):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        up[i][j] = p
for j in range(W):
    p = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        down[i][j] = p

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3) 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin
H, W = [int(_) for _ in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]

left = np.zeros((H,W), dtype=int)
right = np.zeros((H,W), dtype=int)
up = np.zeros((H,W), dtype=int)
down = np.zeros((H,W), dtype=int)

for i in range(H):
    p = 0
    for j in range(W):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        left[i][j] = p
for i in range(H):
    p = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        right[i][j] = p
for j in range(W):
    p = 0
    for i in range(H):
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        up[i][j] = p
for j in range(W):
    p = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            p = 0
        else:
            p += 1
        down[i][j] = p

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3) 

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
  grid += '#' + input() + '#'
grid += '#' * (W+2)

move_list = [1, -1, W+2, -W-2]


def lamp(i):
  sum_ii_cnt = 1
  for move in move_list:
    ii = i
    while True:
      ii += move
      if grid[ii] == '#':
        break
      sum_ii_cnt += 1
  return sum_ii_cnt

ans = 0
for i in range((H+2)*(W+2)):
  if grid[i] != '#':
    ans = max(ans, lamp(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
grid = '#' * (W+2)
for _ in range(H):
  grid += '#' + input() + '#'
grid += '#' * (W+2)
#print(grid)
move_list = [1, -1, W+2, -W-2]


def lamp(i):
  sum_ii_cnt = 1
  for move in move_list:
    ii_cnt = 0
    ii = i
    while True:
      ii += move
      if grid[ii] == '#':
        sum_ii_cnt += ii_cnt
        #print(ii, ii_cnt)
        break
      ii_cnt += 1
  return sum_ii_cnt

ans = 0
for i in range((H+2)*(W+2)):
  if grid[i] == '#':
    continue
  else:
    ans = max(ans, lamp(i))

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()))
def left90(lista):
    listc = []
    for i in zip(*lista):
        listc.append(list(i))
    listc = list(reversed(listc))
    return listc
tranS = left90(S)
def light(h,w):
    if '#' in S[h][w+1:]:
        right = S[h][w:].index('#')+w
    else:
        right = W
    
    if '#' in S[h][:w]:
        left = w-S[h][w::-1].index('#')
    else:
        left = -1

    if '#' in tranS[W-1-w][:h]:
        top = h-tranS[W-1-w][h::-1].index('#')
    else:
        top = -1

    if '#' in tranS[W-1-w][h:]:
        bottom = tranS[W-1-w][h:].index('#') + h
    else:
        bottom = H
    return right-left-1 + bottom-top-1 -1
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] =='.':
            ans = max(ans,light(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [["#" for i in range(W+2)]] + [["#"] + [None for i in range(W)] + ["#"] for j in range(H)] + [["#" for i in range(W+2)]]
right = [[None for i in range(H+2)] for j in range(W+2)]
left = [[None for i in range(H+2)] for j in range(W+2)]
up = [[None for i in range(H+2)] for j in range(W+2)]
down = [[None for i in range(H+2)] for j in range(W+2)]

for i in range(1, H+1):
  S = input()
  for j in range(1, W+1):
    edges[i][j] = S[j-1]

def dfs(x, y):
  flag = 1

  for next in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
    a, b = next
    while edges[b][a] == ".":
      if x - a > 0:
        if left[x][y]:
          flag += left[x][y]
          a -= left[x][y]
          break
        a -= 1
      elif x - a < 0:
        if right[x][y]:
          flag += right[x][y]
          a += right[x][y]
          break
        a += 1
      elif y - b > 0:
        if down[x][y]:
          flag += down[x][y]
          b -= down[x][y]
          break
        b -= 1
      elif y - b < 0:
        if up[x][y]:
          flag += up[x][y]
          b += up[x][y]
          break
        b += 1
      flag += 1

    if x - a > 0:
      left[x][y] = abs(x - a)
    elif x - a < 0:
      right[x][y] = abs(x - a)
    elif y - b > 0:
      down[x][y] = abs(y - b)
    elif y - b < 0:
      up[x][y] = abs(y - b)
  
  return flag

ans = -1
for h in range(1, H+1):
  for w in range(1, W+1):
    if edges[h][w] == "#":
      continue
    ans = max(ans, dfs(w, h))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [["#" for i in range(W+2)]] + [["#"] + [None for i in range(W)] + ["#"] for j in range(H)] + [["#" for i in range(W+2)]]


for i in range(1, H+1):
  S = input()
  for j in range(1, W+1):
    edges[i][j] = S[j-1]

def dfs(x, y):
  flag = 1

  for next in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
    a, b = next
    while edges[b][a] == ".":
      # 直線をキャシュする？
      flag += 1
      if x - a > 0:
        a -= 1
      elif x - a < 0:
        a += 1
      elif y - b > 0:
        b -= 1
      elif y - b < 0:
        b += 1
  
  return flag

ans = -1
for h in range(1, H+1):
  for w in range(1, W+1):
    if edges[h][w] == "#":
      continue
    ans = max(ans, dfs(w, h))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [["#" for i in range(W+2)]] + [["#"] + [None for i in range(W)] + ["#"] for j in range(H)] + [["#" for i in range(W+2)]]

for i in range(1, H+1):
  S = input()
  for j in range(1, W+1):
    edges[i][j] = S[j-1]

def dfs(x, y):
  flag = 1

  for next in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
    a, b = next
    while edges[b][a] == ".":
      flag += 1
      if x - a > 0:
        a -= 1
      elif x - a < 0:
        a += 1
      elif y - b > 0:
        b -= 1
      elif y - b < 0:
        b += 1
  
  return flag

ans = -1
for h in range(1, H+1):
  for w in range(1, W+1):
    if edges[h][w] == "#":
      continue
    ans = max(ans, dfs(w, h))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [["#" for i in range(W+2)]] + [["#"] + [None for i in range(W)] + ["#"] for j in range(H)] + [["#" for i in range(W+2)]]

for i in range(1, H+1):
  S = input()
  for j in range(1, W+1):
    edges[i][j] = S[j-1]

def dfs(x, y):
  flag = 1

  for next in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
    a, b = next
    while edges[b][a] == ".":
      flag += 1
      if x - a > 0:
        a -= 1
      elif x - a < 0:
        a += 1
      elif y - b > 0:
        b -= 1
      elif y - b < 0:
        b += 1
  
  return flag

ans = -1
for h in range(1, H+1):
  for w in range(1, W+1):
    if edges[h][w] == "#":
      continue
    flag = dfs(w, h)
    ans = max(ans, dfs(w, h))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [["#" for i in range(W+2)]] + [["#"] + [None for i in range(W)] + ["#"] for j in range(H)] + [["#" for i in range(W+2)]]
from collections import deque

for i in range(1, H+1):
  S = input()
  for j in range(1, W+1):
    edges[i][j] = S[j-1]

def dfs(x, y):
  if edges[y][x] == "#":
    return []

  flag = [[False for i in range(W+2)] for j in range(H+2)]
  flag[y][x] = True

  for next in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
    a, b = next
    while edges[b][a] == ".":
      flag[b][a] = True
      if x - a > 0:
        a -= 1
      elif x - a < 0:
        a += 1
      elif y - b > 0:
        b -= 1
      elif y - b < 0:
        b += 1
  
  return flag

ans = -1
for h in range(1, H+1):
  for w in range(1, W+1):
    flag = dfs(w, h)
    
    tmp = 0
    for x in flag:
      for y in x:
        if y:
          tmp += 1
    
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())
s = np.array([list(input()) for _ in range(h)])

L = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
D = np.zeros((h, w), dtype=int)

'''
L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
'''
def make(L, R, U, D):
    i = 0
    while i < h:
        j = 0
        while j < w:

#    for i in range(h):
#        for j in range(w):
            if s[i][j] == '#':
                L[i][j] == 0
            elif s[i][j] == '.':
                if j == 0:
                    L[i][j] = 1
                else:
                    L[i][j] = L[i][j-1] + 1

            ri = i
            rj = w-j-1
            if s[ri][rj] == '#':
                R[ri][rj] == 0
            elif s[ri][rj] == '.':
                if rj == w-1:
                    R[ri][rj] = 1
                else:
                    R[ri][rj] = R[ri][rj+1] + 1
        

            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
            
            j += 1
        i += 1

'''
    for j in range(w):
        for i in range(h):
            if s[i][j] == '#':
                D[i][j] == 0
            elif s[i][j] == '.':
                if i == 0:
                    D[i][j] = 1
                else:
                    D[i][j] = D[i-1][j] + 1

            ui = h-i-1
            uj = j
            if s[ui][uj] == '#':
                U[ui][uj] == 0
            elif s[ui][uj] == '.':
                if ui == h-1:
                    U[ui][uj] = 1
                else:
                    U[ui][uj] = U[ui+1][uj] + 1
'''


def right(i, j):
    ui = i-1
    di = i+1
    lj = j-1
    rj = j+1
    cnt = 1

    while ui >= 0 and s[ui][j] != '#':
        ui -= 1 
        cnt += 1

    while di < h and s[di][j] != '#':
        di += 1 
        cnt += 1

    while lj >= 0 and s[i][lj] != '#':
        lj -= 1 
        cnt += 1

    while rj < w and s[i][rj] != '#':
        rj += 1 
        cnt += 1
    #print(i, j, ui, di, lj, rj, cnt)
    return cnt

make(L, R, U, D)

ans = 0
#print(L)
#print(R)
#print(U)
#print(D)

i = 0
while i < h:
    j = 0
    while j < w:
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
        j += 1
    i += 1

'''
for i in range(h):
    for j in range(w):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
'''
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def full(shape, full_value):
    if isinstance(shape, tuple):
        sha = shape[::-1]
        ret = [full_value] * sha[0]
        for s in sha[1:]:
            ret = [ret.copy() for i in range(s)]
        return ret
    else:
        return [full_value] * shape


'''
例
4 6
#..#..
.x...#
....#.
#.#...

明かりは一つだけおく。
全探索なら4*10**6 でギリ間に合わなさそう?

前処理で縦にいくつ照らせるか事前にわかるのでは?(だめ、わからん)

ある点を調べたときにそこが縦にいくつ伸ばせるのか更新していくのは?
→良さそう

'''
H, W = read_ints()
S = read_map(H)
# まわりを壁でfill
MAP = ['#' * (W + 2)]
for s in S:
    MAP.append('#' + s + '#')
MAP.append('#' * (W + 2))


tate = []
yoko = []
for _ in range(H + 2):
    tmp = [0] * (W + 2)
    tate.append(tmp)
for _ in range(H + 2):
    tmp = [0] * (W + 2)
    yoko.append(tmp)

# yokoの構築
for i in range(H + 2):
    pre = '#'
    for j in range(1, W + 2):
        if pre == '#' and MAP[i][j] == '.':
            s = j
            pre = '.'
        if pre == '.' and MAP[i][j] == '#':
            t = j
            cnt = t - s
            pre = '#'
            for k in range(s, t):
                yoko[i][k] = cnt

# tateの構築
for j in range(W + 2):
    pre = '#'
    for i in range(1, H + 2):
        if pre == '#' and MAP[i][j] == '.':
            s = i
            pre = '.'
        if pre == '.' and MAP[i][j] == '#':
            t = i
            cnt = t - s
            pre = '#'
            for k in range(s, t):
                tate[k][j] = cnt

ans = 0
from itertools import product
for i, j in product(range(H + 2), range(W + 2)):
    if MAP[i][j] == '#':
        continue
    ans = max(ans, tate[i][j] + yoko[i][j] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def full(shape, full_value):
    if isinstance(shape, tuple):
        sha = shape[::-1]
        ret = [full_value] * sha[0]
        for s in sha[1:]:
            ret = [ret.copy() for i in range(s)]
        return ret
    else:
        return [full_value] * shape


'''
例
4 6
#..#..
.x...#
....#.
#.#...

明かりは一つだけおく。
全探索なら4*10**6 でギリ間に合わなさそう?

前処理で縦にいくつ照らせるか事前にわかるのでは?(だめ、わからん)

ある点を調べたときにそこが縦にいくつ伸ばせるのか更新していくのは?
→良さそう

'''
H, W = read_ints()
S = read_map(H)
# まわりを壁でfill
MAP = ['#' * (W + 2)]
for s in S:
    MAP.append('#' + s + '#')
MAP.append('#' * (W + 2))


tate = full((H + 2, W + 2), 0)
yoko = full((H + 2, W + 2), 0)

# yokoの構築
for i in range(H + 2):
    pre = '#'
    for j in range(1, W + 2):
        if pre == '#' and MAP[i][j] == '.':
            s = j
            pre = '.'
        if pre == '.' and MAP[i][j] == '#':
            t = j
            cnt = t - s
            pre = '#'
            for k in range(s, t):
                yoko[i][k] = cnt

# tateの構築
for j in range(W + 2):
    pre = '#'
    for i in range(1, H + 2):
        if pre == '#' and MAP[i][j] == '.':
            s = i
            pre = '.'
        if pre == '.' and MAP[i][j] == '#':
            t = i
            cnt = t - s
            pre = '#'
            for k in range(s, t):
                tate[k][j] = cnt

ans = 0
from itertools import product
for i, j in product(range(H + 2), range(W + 2)):
    if MAP[i][j] == '#':
        continue
    ans = max(ans, tate[i][j] + yoko[i][j] - 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

l = np.zeros((h+2, w+2), dtype=int)
r = np.zeros((h+2, w+2), dtype=int)
u = np.zeros((h+2, w+2), dtype=int)
d = np.zeros((h+2, w+2), dtype=int)

for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i-1][j-1] == '.':
            l[i, j] = l[i, j-1] + 1
            u[i, j] = u[i-1, j] + 1
for i in reversed(range(1, h+1)):
    for j in reversed(range(1, w+1)):
        if s[i-1][j-1] == '.':
            r[i, j] = r[i, j+1] + 1
            d[i, j] = d[i+1, j] + 1

print((r+l+u+d - 3).max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

xh = []
for t in s:
    y = np.zeros(w, dtype=int)
    if t[0] == '.':
        y[0] = 1
    for i, u in enumerate(t[1:]):
        if u == '.':
            y[i+1] = y[i] + 1
        else:
            y[i+1-(y[i]):i+1] = y[i]
    if t[-1] == '.':
        y[-y[-1]:] = y[-1]
    xh.append(y)
xh = np.array(xh)

xv = []
for i in range(w):
    t = [s_[i] for s_ in s]
    y = np.zeros(h, dtype=int)
    if t[0] == '.':
        y[0] = 1
    for i, u in enumerate(t[1:]):
        if u == '.':
            y[i+1] = y[i] + 1
        else:
            y[i+1-(y[i]):i+1] = y[i]
    if t[-1] == '.':
        y[-y[-1]:] = y[-1]
    xv.append(y)
xv = np.array(xv).T

print((xv + xh - 1).max())