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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

H,W = IL()
S = SLs(H)

YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  
YOKO = []
for s in S:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  YOKO.append(yoko)
  
TENTI = [list(i) for i in zip(*S)]

TATE = []
for s in TENTI:
  prev = None
  yoko = []
  count = 0
  for item in s:
    if item == prev == ".":
      count += 1
    elif prev == "." and item == "#":
      yoko += [count]*count + [0]
      count = 0
    elif prev != "." and item == ".":
      count = 1
    else:
      yoko += [0]
    prev = item
  yoko += [count]*count
  TATE.append(yoko)
TATE = [list(i) for i in zip(*TATE)]

print(max(max(TATE[i][j]+YOKO[i][j] for j in range(W)) for i in range(H))-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [input() for _ in range(h)]
hrz = [[0] * w for _ in range(h)]
vrt = [[0] * w for _ in range(h)]
for i in range(h):
    cnt = 0
    for j in range(w + 1):
        if j < w and s[i][j] == '.':
            if cnt == 0:
                start = j
            cnt += 1
        elif cnt > 0:
            for k in range(start, j):
                hrz[i][k] = cnt
            cnt = 0
for j in range(w):
    cnt = 0
    for i in range(h + 1):
        if i < h and s[i][j] == '.':
            if cnt == 0:
                start = i
            cnt += 1
        elif cnt > 0:
            for k in range(start, i):
                vrt[k][j] = cnt
            cnt = 0
ans = max(hrz[i][j] + vrt[i][j] - 1 for i in range(h) for j in range(w))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict
    h, w = map(int, input().split())
    m = []
    o = []
    for _ in range(h):
        s = input()
        m.append(s)
        o.append(list(s))

    t = []
    for u in zip(*o):
        t.append(''.join(u))

    mr = [[0] * w for _ in range(h)]
    ml = [[0] * h for _ in range(w)]
    ans = 0
    for i in range(h):
        row = m[i]
        for j in range(w):
            col = t[j]
            if col[i] == '#':
                continue

            if mr[i][j]:
                c_row = mr[i][j]
            else:
                a, b = row[:j].rfind('#'), row[j + 1:].find('#')
                crl = j if a == -1 else j - 1 - a
                crr = w - j - 1 if b == -1 else b
                c_row = crl + crr
                # [j - crl, j + crr + 1)
                for k in range(j - crl, j + crr + 1):
                    mr[i][k] = c_row

            if ml[j][i]:
                c_col = ml[j][i]
            else:
                a, b = col[:i].rfind('#'), col[i + 1:].find('#')
                cll = i if a == -1 else i - 1 - a
                clr = h - i - 1 if b == -1 else b
                c_col = cll + clr
                # [i - cll, i + clr + 1)
                for k in range(i - cll, i + clr + 1):
                    ml[j][k] = c_col

            cnt = c_row + c_col + 1
            ans = max(ans, cnt)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from bisect import bisect_left as bl
    h, w = map(int, input().split())
    m = []
    row = []

    col = [[] for _ in range(w + 1)]
    for i in range(h):
        r = sys.stdin.readline()
        s = [-1] + [j for j, l in enumerate(r) if l == '#'] + [w]
        m.append(r)
        row.append(s)
        for k in s:
            col[k].append(i)

    ans = 0
    for i in range(h):
        r = row[i]
        for j in range(w):
            if m[i][j] == '#':
                continue
            l = [-1] + col[j] + [h]
            x, y = bl(r, j), bl(l, i)
            ans = max(ans, r[x] - r[x - 1] + l[y] - l[y - 1] - 3)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import numpy as np

    h, w = map(int, input().split())
    m = []
    r = []

    for i in range(h):
        s = np.array(list(input()))
        m.append(s)
        l = [-1] + list(np.where(s == '#')[0]) + [w]
        arr = np.array([0] * w)
        for p, q in zip(l, l[1:]):
            arr[p + 1:q] = q - p - 1
        r.append(arr)

    m = np.array(m)
    r = np.array(r)

    for j in range(w):
        s = m[:, j]
        l = [-1] + list(np.where(s == '#')[0]) + [h]
        for p, q in zip(l, l[1:]):
            r[p + 1:q, j] += q - p - 1

    print(np.max(r) - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import numpy as np

    h, w = map(int, input().split())
    m = []
    r = []

    for i in range(h):
        s = input()
        t = [[0] if x == '?' else [len(x)] * len(x) for x in s.replace('#', '#?#').rsplit('#')]

        m.append(list(s))
        r.append(sum(t, []))

    m = np.array(m)
    r = np.array(r)

    for j in range(w):
        s = ''.join(m[:, j])
        t = [[0] if x == '?' else [len(x)] * len(x) for x in s.replace('#', '#?#').rsplit('#')]
        r[:, j] += np.array(sum(t, []))

    print(np.max(r) - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve(sh,sw):
  if S[sh][sw]=="#":
    return 0
  h,w=sh,sw
  cnt=1
  for _ in range(H):
    if h==0:
      break
    h-=1
    if S[h][w]=="#":
      break
    cnt+=1
  h=sh
  for _ in range(H):
    if h==H-1:
      break
    h+=1
    if S[h][w]=="#":
      break
    cnt+=1
  h=sh
  for _ in range(W):
    if w==0:
      break
    w-=1
    if S[h][w]=="#":
      break
    cnt+=1
  w=sw
  for _ in range(W):
    if w==W-1:
      break
    w+=1
    if S[h][w]=="#":
      break
    cnt+=1
  return cnt

ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,solve(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    import numpy as np
    from itertools import groupby
    h, w = map(int, input().split())
    m = []

    for i in range(h):
        m.append(list(sys.stdin.readline()))

    m = np.array(m)
    m = m == '.'

    c = np.zeros((h, w), dtype=int)
    for i in range(h):
        l = 0
        for k, gr in groupby(m[i, :]):
            x = len(list(gr))
            r = l + x
            c[i, l:r] += x * k
            l = r

    for j in range(w):
        l = 0
        for k, gr in groupby(m[:, j]):
            y = len(list(gr))
            r = l + y
            c[l:r, j] += y * k
            l = r

    print(np.max(c) - 1)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict
    h, w = map(int, input().split())
    m = []
    o = []
    for _ in range(h):
        s = input()
        m.append(s)
        o.append(list(s))

    t = []
    for u in zip(*o):
        t.append(''.join(u))

    mr = [[None] * w for _ in range(h)]
    ml = [[None] * h for _ in range(w)]
    for i in range(h):
        row = m[i]
        for j in range(w):
            col = t[j]
            if col[i] == '#':
                continue
            if mr[i][j] is None:
                a, b = row[:j].rfind('#'), row[j + 1:].find('#')
                crl = j if a == -1 else j - 1 - a
                crr = w - j - 1 if b == -1 else b
                c_row = crl + crr
                # [j - crl, j + crr + 1)
                for k in range(j - crl, j + crr + 1):
                    mr[i][k] = c_row

            if ml[j][i] is None:
                a, b = col[:i].rfind('#'), col[i + 1:].find('#')
                cll = i if a == -1 else i - 1 - a
                clr = h - i - 1 if b == -1 else b
                c_col = cll + clr
                # [i - cll, i + clr + 1)
                for k in range(i - cll, i + clr + 1):
                    ml[j][k] = c_col

    ans = 0
    for i in range(h):
        for j in range(w):
            if m[i][j] == '#':
                continue
            else:
                ans = max(ans, mr[i][j] + ml[j][i] + 1)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

h, w = list(map(int, input().split()))

s = [list(input()) for _ in range(h)]

data_w = []
data_w_index = []
data_h = []
data_h_index = []

for i in range(h):
    count = 0
    index = 0
    data_w_index_tmp = []
    data_w_tmp = []
    for j in range(len(s[i])):
        # print(s[i][j][0])
        # print(count)
        # print(index)
        if s[i][j] == ".":
            count += 1
            data_w_index_tmp.append(index)
        else:
            data_w_tmp.append(count)
            data_w_index_tmp.append(-1)
            count = 0
            index += 1
    data_w_tmp.append(count)
    # data_w_index_tmp.append(index)

    data_w_index.append(data_w_index_tmp)
    data_w.append(data_w_tmp)

# print(data_w)
# print(data_w_index)

for i in range(w):
    count = 0
    index = 0
    data_h_index_tmp = []
    data_h_tmp = []
    for j in range(len(s)):
        # print(s[i][j][0])
        # print(count)
        # print(index)
        if s[j][i] == ".":
            count += 1
            data_h_index_tmp.append(index)
        else:
            data_h_tmp.append(count)
            data_h_index_tmp.append(-1)
            count = 0
            index += 1
    data_h_tmp.append(count)
    # data_h_index_tmp.append(index)

    data_h_index.append(data_h_index_tmp)
    data_h.append(data_h_tmp)

# print(data_h)
# print(data_h_index)

ans = 0
for i in range(w):
    for j in range(h):
        index_h = data_h_index[i][j]
        index_w = data_w_index[j][i]
        if index_h != 1:
            ans_tmp = data_h[i][index_h]+data_w[j][index_w]-1
            ans = max(ans, ans_tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

h, w = map(int, input().split())
iswall = []
for _ in range(h):
    s = input()
    iswall.append([int(c == '#') for c in s])


def getll():
    ls = [[None] * w for _ in range(h)]
    for ih in range(h):
        l = 0
        for iw in range(w):
            if not iswall[ih][iw]:
                l += 1
            else:
                l = 0
            ls[ih][iw] = l
    return ls


def getlr():
    ls = [[None] * w for _ in range(h)]
    for ih in range(h):
        l = 0
        for iw in range(w - 1, -1, -1):
            if not iswall[ih][iw]:
                l += 1
            else:
                l = 0
            ls[ih][iw] = l
    return ls


def getlu():
    ls = [[None] * w for _ in range(h)]
    for iw in range(w):
        l = 0
        for ih in range(h):
            if not iswall[ih][iw]:
                l += 1
            else:
                l = 0
            ls[ih][iw] = l
    return ls


def getld():
    ls = [[None] * w for _ in range(h)]
    for iw in range(w):
        l = 0
        for ih in range(h - 1, -1, -1):
            if not iswall[ih][iw]:
                l += 1
            else:
                l = 0
            ls[ih][iw] = l
    return ls


ll = getll()
lr = getlr()
lu = getlu()
ld = getld()

m = 0
for ih, iw in product(range(h), range(w)):
    light = ll[ih][iw] + lr[ih][iw] + lu[ih][iw] + ld[ih][iw] - 3
    m = max(m, light)

print(m)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '#':
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
s = [input() for _ in range(H)]
ans = [[-1 for w in range(W)] for h in range(H)]
ans0 = ans[:]
for h in range(H):
    sh = s[h]
    st = -1
    gl = -1
    cnt = 0
    for w in range(W):
        if sh[w] == '.':
            cnt += 1
            if st == -1:
                st,gl = w,w
            gl +=1
            if w == W-1:
                for i in range(st,w+1):
                    ans[h][i] += cnt
        else:
            for i in range(st,gl):
                ans[h][i] += cnt
            cnt = 0
            st,gl = -1,-1
#print(*ans,sep='\n')
#ans1 = ans[:]
#ans = [[0 for w in range(W)] for h in range(H)]
for w in range(W):
    st = -1
    gl = -1
    cnt = 0
    for h in range(H):
        if s[h][w] == '.':
            cnt += 1
            if st == -1:
                st,gl = h,h
            gl +=1
            if h == H-1:
                for i in range(st,h+1):
                    ans[i][w] += cnt
        else:
            for i in range(st,gl):
                ans[i][w] += cnt
            cnt = 0
            st,gl = -1,-1
#print(*ans,sep='\n')
mx = 0
for x in ans:
    mx = max(max(x),mx)
print(mx)

Submission status: Time Limit Exceeded

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

Ss = []
for _ in range(H):
    s = list(input())
    Ss.append(s)

# 各マスから左に何マスいったら壁にぶつかるか
left = [[-1 for _ in range(W)] for _ in range(H)]
right = [[-1 for _ in range(W)] for _ in range(H)]
top = [[-1 for _ in range(W)] for _ in range(H)]
bottom = [[-1 for _ in range(W)] for _ in range(H)]


# 左に何マスいったらぶつかるか
for i in range(H):
    count = 0
    for j in range(W):
        if Ss[i][j] == "#":
            count = 0
        else:
            left[i][j] = count
            count += 1

# 右に何マスいったらぶつかるか
for i in range(H):
    count = 0
    for j in range(W):
        k = W-j-1
        if Ss[i][k] == "#":
            count = 0
        else:
            right[i][k] = count
            count += 1

# 上に何マスいったらぶつかるか
for j in range(W):
    count = 0
    for i in range(H):
        if Ss[i][j] == "#":
            count = 0
        else:
            top[i][j] = count
            count += 1

# 下に何マスいったらぶつかるか
for j in range(W):
    count = 0
    for i in range(H):
        k = H - i - 1
        if Ss[k][j] == "#":
            count = 0
        else:
            bottom[k][j] = count
            count += 1

# print("right")
# for i in range(H):
#     print(right[i])
#
# print("left")
# for i in range(H):
#     print(left[i])
#
# print("bottom")
# for i in range(H):
#     print(bottom[i])
#
# print("top")
# for i in range(H):
#     print(top[i])

max_score = 0
for i in range(H):
    for j in range(W):
        if Ss[i][j] != "#":
            score = left[i][j] + right[i][j] + top[i][j] + bottom[i][j] + 1
            max_score = max(max_score, score)

print(max_score)

Submission status: Time Limit Exceeded

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

Ss = []
for _ in range(H):
    s = list(input())
    Ss.append(s)

# 各マスから左に何マスいったら壁にぶつかるか
left = [[-1 for _ in range(W)] for _ in range(H)]
right = [[-1 for _ in range(W)] for _ in range(H)]
top = [[-1 for _ in range(W)] for _ in range(H)]
bottom = [[-1 for _ in range(W)] for _ in range(H)]


# 左に何マスいったらぶつかるか
for i in range(H):
    count = 0
    for j in range(W):
        if Ss[i][j] == "#":
            count = 0
        else:
            left[i][j] = count
            count += 1

# 右に何マスいったらぶつかるか
for i in range(H):
    count = 0
    for j in range(W):
        k = W-j-1
        if Ss[i][k] == "#":
            count = 0
        else:
            right[i][k] = count
            count += 1

# 上に何マスいったらぶつかるか
for j in range(W):
    count = 0
    for i in range(H):
        if Ss[i][j] == "#":
            count = 0
        else:
            top[i][j] = count
            count += 1

# 下に何マスいったらぶつかるか
for j in range(W):
    count = 0
    for i in range(H):
        k = H - i - 1
        if Ss[k][j] == "#":
            count = 0
        else:
            bottom[k][j] = count
            count += 1

# print("right")
# for i in range(H):
#     print(right[i])
#
# print("left")
# for i in range(H):
#     print(left[i])
#
# print("bottom")
# for i in range(H):
#     print(bottom[i])
#
# print("top")
# for i in range(H):
#     print(top[i])




max_score = 0
for i in range(H):
    for j in range(W):
        if Ss[i][j] != "#":
            score = left[i][j] + right[i][j] + top[i][j] + bottom[i][j] + 1
            max_score = max(max_score, score)

print(max_score)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
r = [[0]*w for _ in range(h)]
for i in range(h):
    flg = False
    row = s[i]
    row2 = r[i]
    for j in range(w):
        if row[j]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and row[j]=='#':
            for k in range(begin, j):
                row2[k] = tmp
            flg = False
    if flg:
        for k in range(begin, w):
            row2[k] = tmp
c = [[0]*w for _ in range(h)]
for i in range(w):
    flg = False
    for j in range(h):
        if s[j][i]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[j][i]=='#':
            for k in range(begin, j):
                c[k][i] = tmp
            flg = False
    if flg:
        for k in range(begin, h):
            c[k][i] = tmp
ans = 0
for row1, row2 in zip(r, c):
    for e1, e2 in zip(row1, row2):
        if ans<e1+e2-1:
            ans = e1+e2-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
S = [input() for _ in range(h)]
hs = [0] * h
ws = [0] * w
for i in range(h):
    piyo = 0
    hoge = []
    for j in range(w):
        s = S[i][j]
        if s == ".":
            piyo += 1
            hoge.append(j)
        else:
            for k in hoge:
                ws[k] = max(ws[k], piyo)
            piyo = 0
            hoge = []
    for k in hoge:
        ws[k] = max(ws[k], piyo)
for i in range(w):
    piyo = 0
    hoge = []
    for j in range(h):
        s = S[j][i]
        if s == ".":
            piyo += 1
            hoge.append(j)
        else:
            for k in hoge:
                hs[k] = max(hs[k], piyo)
            piyo = 0
            hoge = []
    for k in hoge:
        hs[k] = max(hs[k], piyo)   
result = 0
for i in range(h):
    for j in range(w):
        result = max(result, hs[i] + ws[j] - 1)
print(result)

Submission status: Time Limit Exceeded

Solution code:
h , w = map(int,input().split())
giri = [list(input()) for i in range(h)]
ans = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    sta = -1
    cou = 0
    for j in range(w):
        if sta == -1 and giri[i][j] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[i][j] == ".":
            cou += 1
        elif sta != -1 and giri[i][j] == "#":
            for k in range(sta,j):
                ans[i][k] += cou
            cou = 0
            sta = -1
        if j == w-1 and sta != -1:
            for k in range(sta,w):
                ans[i][k] += cou

for i in range(w):
    sta = -1
    cou = 0
    for j in range(h):
        if sta == -1 and giri[j][i] == ".":
            sta = j
            cou += 1
        elif sta != -1 and giri[j][i] == ".":
            cou += 1
        elif sta != -1 and giri[j][i] == "#":
            for k in range(sta,j):
                ans[k][i] += cou
            cou = 0
            sta = -1
        if j == h-1 and sta != -1:
            for k in range(sta,h):
                ans[k][i] += cou

kotae = 0

for i in range(h):
    for j in range(w):
        kotae = max(kotae,ans[i][j]-1)

print(kotae)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


mod = 10 ** 9 + 7
H, W = list(map(int, input().split()))
S = ['']*H
for i in range(H):
    S[i] = input()


L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
A = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if S[i][j] == '.' and j == 0:
            L[i][j] = 1
        elif (S[i][j] == '.'):
            L[i][j] = L[i][j - 1] + 1

for i in range(H):
    for j in reversed(range(W)):
        if S[i][j] == '.' and j == (W-1):
            R[i][j] = 1
        elif (S[i][j] == '.'):
            R[i][j] = R[i][j + 1] + 1


for i in range(H):
    for j in range(W):
        if S[i][j] == '.' and i == 0:
            U[i][j] = 1
        elif (S[i][j] == '.'):
            U[i][j] = U[i-1][j] + 1


for i in reversed(range(H)):
    for j in range(W):
        if S[i][j] == '.' and i == (H-1):
            D[i][j] = 1
        elif (S[i][j] == '.'):
            D[i][j] = D[i+1][j] + 1
ans = 0

for i in reversed(range(H)):
    for j in range(W):
        # A[i][j] = R[i][j] + L[i][j] + U[i][j] + D[i][j] - 3
        # if (ans < R[i][j] + L[i][j] + U[i][j] + D[i][j] - 3):
        #     ans = R[i][j] + L[i][j] + U[i][j] + D[i][j] - 3
        #     # hoge = [i, j]
        ans = max(ans, R[i][j] + L[i][j] + U[i][j] + D[i][j] - 3)
# print(ans)
# print(hoge)
# print('=========L=========')
# for i in range(H):
#     print(L[i])
# print('======R===========')
# for i in range(H):
#     print(R[i])
# print('=======U==========')
# for i in range(H):
#     print(U[i])
# print('========D==========')
# for i in range(H):
#     print(D[i])

# for i in range(H):
#     print(A[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def burst(S,H,W):
    for i in range(H):
        S[i] += "d" #dummy
    S.append("d" * (W+1))
    tate_burst = [[] for _ in range(W)]
    yoko_burst = [[] for _ in range(H)]
    #tate_burst[j]:j列目の連続する"."の(左端,右端)
    #yoko_burst[i]:i行目の連続する"."の(上端,下端)

    for j in range(W):
        sp,ep = None,None
        for i in range(H):
            if S[i][j] == ".":
                if sp == None:
                    sp = i
                    if S[i+1][j] != ".":
                        ep = i
                        tate_burst[j].append((sp,ep))
                        sp,ep = None,None
                elif S[i+1][j] != ".":
                    ep = i
                    tate_burst[j].append((sp,ep))
                    sp,ep = None,None

    for i in range(H):
        sp,ep = None,None
        for j in range(W):
            if S[i][j] == ".":
                if sp == None:
                    sp = j
                    if S[i][j+1] != ".":
                        ep = j
                        yoko_burst[i].append((sp,ep))
                        sp,ep = None,None
                elif S[i][j+1] != ".":
                    ep = j
                    yoko_burst[i].append((sp,ep))
                    sp,ep = None,None

    return tate_burst,yoko_burst

def score(tate_burst,yoko_burst,H,W):
    T = [[-1 for _ in range(W)] for _ in range(H)]

    for j in range(W):
        for st,go in tate_burst[j]:
            for i in range(st,go+1):
                T[i][j] += (go-st+1)

    for i in range(H):
        for st,go in yoko_burst[i]:
            for j in range(st,go+1):
                T[i][j] += (go-st+1)

    return T

def max_score(T,H,W):
    output = 0
    for i in range(H):
        for j in range(W):
            output = max(output,T[i][j])

    return output

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

    B = burst(S,H,W)
    tate_burst,yoko_burst = B[0],B[1]
    T = score(B[0],B[1],H,W)
    ans = max_score(T,H,W)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def yokocalc(sx, sy):
  que = deque([])
  que.append((sx, sy))
  ans = 1
  # 移動4方向のベクトル
  dx = [1, -1]
  dy = [0, 0]
    
  for i in range(2):
    posx = sx
    posy = sy
    flg = True
    while flg:
      nx = posx + dx[i]
      ny = posy + dy[i]
      if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#":
        posx = nx
        posy = ny
        ans += 1
      else:
        flg = False
  while que:
    p = que.popleft()
    yoko[p[0]][p[1]] = ans         
  return

def tatecalc(sx, sy):
  que = deque([])
  que.append((sx, sy))
  ans = 1
  # 移動4方向のベクトル
  dx = [0, 0]
  dy = [1, -1]
    
  for i in range(2):
    posx = sx
    posy = sy
    flg = True
    while flg:
      nx = posx + dx[i]
      ny = posy + dy[i]
      if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#":
        posx = nx
        posy = ny
        ans += 1
      else:
        flg = False
  while que:
    p = que.popleft()
    tate[p[0]][p[1]] = ans         
  return 
  
n, m = map(int, input().split())

maze = [list(input()) for i in range(n)]
tate = [[0] * m for i in range(n)] #縦に照らせる数
yoko = [[0] * m for i in range(n)] #横に照らせる数
ans2 = 0

for i in range(n):
  for j in range(m):
    if maze[i][j] != "#":
      if tate[i][j] == 0:
        tatecalc(i, j)
      if yoko[i][j] == 0:
        yokocalc(i, j)
      temp = tate[i][j] + yoko[i][j]-1
      if temp > ans2:
        ans2 = temp

    
print(ans2)

Submission status: Time Limit Exceeded

Solution code:
def bfs(sx, sy):
 
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    ans = 1
    
    for i in range(4):
      posx = sx
      posy = sy
      flg = True
      while flg:
        nx = posx + dx[i]
        ny = posy + dy[i]
        if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#":
          posx = nx
          posy = ny
          ans += 1
        else:
          flg = False
             
    return ans
 
 
n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
 
ans = 0
for i in range(n):
  for j in range(m):
    if maze[i][j] != "#":
      temp = bfs(i,j)
      if temp >= ans:
        ans = temp
        x = i
        y = j
    
print(ans)