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 = [list(input()) for h in range(H)]
ST = [[row[w] for row in S] for w in range(W)]
count_matw = [[0 for w in range(W)]for h in range(H)]
count_math = [[0 for w in range(W)]for h in range(H)]

for h in range(H):
    row = S[h]
    for w in range(W):
        if w > 0 and row[w] != '#' and count_matw[h][w-1] != 0:
            count_matw[h][w] = count_matw[h][w-1]
            continue
        if '#' in row[w:]:
            obs_i = row[w:].index('#')
            count_matw[h][w] = obs_i
        else:
            count_matw[h][w] = W-w
for w in range(W):
    col = ST[w]
    for h in range(H):
        if h > 0 and col[h] != '#' and count_math[h-1][w] != 0:
            count_math[h][w] = count_math[h-1][w]
            continue
        if '#' in col[h:]:
            obs_i = col[h:].index('#')
            count_math[h][w] = obs_i
        else:
            count_math[h][w] = H-h
ans = max([count_math[h][w] + count_matw[h][w]for h in range(H) for w in range(W)])
print(ans-1)

Submission status: Time Limit Exceeded

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

def f(H, W, S):
    hs = [[0]*W for i in range(H)]
    vs = [[0]*W for i in range(H)]
    sts = [0]*(W+1)

    for j, s in enumerate(S):
        st = 0
        
        for i, c in enumerate(s):
            if c == '#':
                if st < i:
                    sz = i-st
                    for k in range(st, i):
                        hs[j][k] = sz
                st = i+1

                if sts[i] < j:
                    sz = j-sts[i]
                    for k in range(sts[i], j):
                        vs[k][i] = sz

                sts[i] = j+1

    m = 0
    for j in range(H):
        for i in range(W):
            m = max(m,  hs[j][i] + vs[j][i] - 1)


    return m


def main():
    H,W = map(int, input().split())
    S = list(input() + '#' for i in range(H))
    S.append('#'*W)

    print(f(H, W, S))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
INPUT = sys.stdin.readline

def SINGLE_INT(): return int(INPUT())
def MULTIPLE_INT_LIST(): return list(map(int, INPUT().split()))
def MULTIPLE_INT_MAP(): return map(int, INPUT().split())
def SINGLE_STRING(): return INPUT()
def MULTIPLE_STRING(): return INPUT().split()

Y, X = MULTIPLE_INT_MAP()
encode = {'#': 1, '.' : 0}

grid = [[encode[x] for x in input()] for _ in range(Y)]
row_lighting = [[0 for _ in range(X)] for _ in range(Y)]
col_lighting = [[0 for _ in range(X)] for _ in range(Y)]

for row in range(Y):
    col, start, streak = 0, 0, 0
    while col < X:
        if grid[row][col]: # obstacle
            if streak == 0:
                start = col = col + 1
                continue
            else:
                for i in range(start, col):
                    row_lighting[row][i] = streak
                start = col = col + 1
                streak = 0

        else:
            streak += 1

            if col == X - 1:
                for i in range(start, X):
                    row_lighting[row][i] = streak
                start = col = col + 1
                streak = 0

            else:
                col += 1

for col in range(X):
    row, start, streak = 0, 0, 0
    while row < Y:
        if grid[row][col]: # obstacle
            if streak == 0:
                start = row = row + 1
                continue
            else:
                for i in range(start, row):
                    col_lighting[i][col] = streak
                start = row = row + 1
                streak = 0

        else:
            streak += 1

            if row == Y - 1:
                for i in range(start, Y):
                    col_lighting[i][col] = streak
                start = row = row + 1
                streak = 0

            else:
                row += 1

ans = float('-inf')
current = 0
MAX = X + Y - 1

for row in range(Y):
    for col in range(X):
        current = row_lighting[row][col] + col_lighting[row][col] - 1
        ans = max(ans, current)
        if ans == MAX:
            break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main():
    H, W = LI()
    S = []
    for _ in range(H):
        S.append(SI())

    # print(S)

    # 横方向に探索
    yoko = [ [-1]*W for _ in range(H)]
    for i in range(H):
        beginning = True
        continuous = 0
        for j in range(W):
            if beginning:
                if S[i][j] == '#':
                    continue
                if S[i][j] == '.':
                    beginning = False
                    continuous += 1
            else:
                if S[i][j] == '#':
                    for k in range(j-continuous, j):
                        yoko[i][k] = continuous
                    beginning = True
                    continuous = 0
                if S[i][j] == '.':
                    continuous += 1
        if continuous:
            for k in range(W-continuous, W):
                yoko[i][k] = continuous

    # 縦方向に探索
    tate = [ [-1]*W for _ in range(H)]
    for j in range(W):
        beginning = True
        continuous = 0
        for i in range(H):
            if beginning:
                if S[i][j] == '#':
                    continue
                if S[i][j] == '.':
                    beginning = False
                    continuous += 1
            else:
                if S[i][j] == '#':
                    for k in range(i-continuous, i):
                        tate[k][j] = continuous
                    beginning = True
                    continuous = 0
                if S[i][j] == '.':
                    continuous += 1
        if continuous:
            for k in range(H-continuous, H):
                tate[k][j] = continuous

    ans = 1  # ぜったい1マスは光る。
    for i in range(H):
        for j in range(W):
            ans = max(ans, tate[i][j] + yoko[i][j] - 1)

    print(ans)


main()

Submission status: Time Limit Exceeded

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

field = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
  s = s_s[i]
  for j in range(w):
    if s[j: j+1] == '#':
      field[i][j] = 1
  
hori_score = [[0 for _ in range(w)] for _ in range(h)]
vert_score = [[0 for _ in range(w)] for _ in range(h)]

#横方向
for i in range(h):
  #連続領域のスコアリング
  #まずカウントアップ
  score = 0
  for j in range(w):
    if field[i][j] == 0:
      score += 1
    else:
      score = 0
    hori_score[i][j] = score

  #当該マスと右マスが空きなら右マスのスコアをコピー
  for j in range(w - 2, -1, -1):
    if field[i][j] == 0 and field[i][j + 1] == 0:
      hori_score[i][j] = hori_score[i][j+1]
    
#縦方向
for j in range(w):
  score = 0
  #連続領域のスコアリング
  #まずカウントアップ
  for i in range(h):
    if field[i][j] == 0:
      score += 1
    else:
      score = 0
    vert_score[i][j] = score

  #当該マスと下マスが空きなら右マスのスコアをコピー
  for i in range(h - 2, -1, -1):
    if field[i][j] == 0 and field[i + 1][j] == 0:
      vert_score[i][j] = vert_score[i + 1][j]
    

max_score = 0
for i in range(h):
  for j in range(w):
    if field[i][j] == 0:
      cand = hori_score[i][j] + vert_score[i][j]
      if max_score < cand:
        max_score = cand

#print(hori_score)
#print(vert_score)
print(max_score-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
h+=2
w+=2
s=[]
l=[[0 for i in range(w)]for j in range(h)]
s.append(["#" for i in range(w)])
for i in range(h-2):
    a=input()
    s.append("#"+a+"#")
s.append(["#" for i in range(w)])

yl=[[]for j in range(h)]
tl=[[]for j in range(w)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            yl[i].append(j)
            tl[j].append(i)
ans=0
import bisect
for i in range(1,h-1):
    for j in range(1,w-1):
        if s[i][j]!="#":
            n=bisect.bisect(yl[i],j)
            m=bisect.bisect(tl[j],i)
            p=0
            if yl[i][n-1]!=yl[i][-1]:
                p+=yl[i][n]-yl[i][n-1]-1
            elif j<yl[i][0]:
                p+=yl[i][0]
            else:
                p+=len(yl[i])-yl[i][-1]-1
                
            if tl[j][m-1]!=tl[j][-1]:
                p+=tl[j][m]-tl[j][m-1]-2
            elif i<tl[j][0]:
                p+=tl[j][0]-1
            else:
                p+=len(tl[j])-tl[j][-1]-2
            
            ans=max(ans,p)
                
        
print(ans)

Submission status: Time Limit Exceeded

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

S = []
for i in range(H):
    S.append(input())

b = [[[0, 0, 0, 0] for w in range(W)] for h in range(H)]
m = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            m[h][w] = 1

for h in range(H):
    for w in range(W):
        if m[h][w] == 1:
            continue
        # up
        if h-1 < 0 or m[h-1][w] == 1:
            b[h][w][0] = 0
        else:
            b[h][w][0] = b[h-1][w][0] + 1
        # left
        if w-1 < 0 or m[h][w-1] == 1:
            b[h][w][1] = 0
        else:
            b[h][w][1] = b[h][w-1][1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if m[h][w] == 1:
            continue
        # down
        if h+1 >= H or m[h+1][w] == 1:
            b[h][w][2] = 0
        else:
            b[h][w][2] = b[h+1][w][2] + 1
        # right
        if w+1 >= W or m[h][w+1] == 1:
            b[h][w][3] = 0
        else:
            b[h][w][3] = b[h][w+1][3] + 1

#for h in range(H):
#    print(b[h])
ans = 0
for h in range(H):
    for w in range(W):
        if m[h][w] == 1:
            continue
        tmp = sum(b[h][w]) + 1
        if tmp > ans:
            ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=(int(i) for i in input().split())
a=[]
b=[]
q=0
for i in range(h):
  s=input()
  r=[]
  c=0
  for j in range(w):
    if s[j]==".":
      c=c+1
      if j==w-1:
        for k in range(c):
          r.append(c)
    elif s[j]=="#":
      for k in range(c):
        r.append(c)
      r.append(0)
      c=0
  a.append(r)
for i in range(w):
  r=[]
  c=0
  for j in range(h):
    if a[j][i]!=0:
      c=c+1
      if j==h-1:
        for k in range(c):
          r.append(c)
    elif a[j][i]==0:
      for k in range(c):
        r.append(c)
      r.append(0)
      c=0
  b.append(r)
for i in range(h):
  for j in range(w):
    if a[i][j]+b[j][i]-1>q:
      q=a[i][j]+b[j][i]-1
print(q)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W=map(int,input().split())
L=[]
l=["#" for i in range(W+2)]
L.append(l)
#print(L)
for i in range(H):
    s=list(input().rstrip())
    s=["#"]+s+["#"]
    L.append(s)
L.append(s)

#print(L)
A=[[[0,0,0,0]for i in range(W+2)]for j in range(H+2)]
#print(A)
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]==".":
            A[i][j][0]=A[i][j-1][0]+1
            A[i][j][1]=A[i-1][j][1]+1
#print(A)
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[H+1-i][W+1-j]==".":
            A[H+1-i][W+1-j][2]=A[H+1-i][W+2-j][2]+1
            A[H+1-i][W+1-j][3]=A[H+2-i][W+1-j][3]+1
#print(A)
ANS=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if (sum(A[i][j])-3)>ANS:
            ANS=(sum(A[i][j])-3)
print(ANS)

Submission status: Time Limit Exceeded

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

x_int = [-4000]
y_int = [-4000]
x_index = [[] for i in range(H)]
y_index = [[] for i in range(H)]

index = 1
for i in range(H):
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            # print("i: " + str(i) + " j: " + str(j))
            tmp += 1
            x_index[i].append(index)
        else:
            x_index[i].append(0)
            x_int.append(tmp)
            index += 1
            tmp = 0
    if tmp != 0:
        x_int.append(tmp)
        index += 1


index = 1
for i in range(W):
    tmp = 0
    for j in range(H):
        if S[j][i] == '.':
            tmp += 1
            y_index[j].append(index)
        else:
            y_index[j].append(0)
            y_int.append(tmp)
            index += 1
            tmp = 0
    if tmp != 0:
        y_int.append(tmp)
        index += 1
ans = 0
for i in range(H):
    for j in range(W):
        t = x_int[x_index[i][j]] + y_int[y_index[i][j]]
        if ans < t:
            ans = t
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
s = np.zeros((H, W), np.int64)


def conv(c):
    if c == '#':
        return -1
    else:
        return 0


for i in range(H):
    l = input()
    for j in range(W):
        s[i][j] = conv(l[j])

for i in range(H):
    n = 0
    prev = 0
    for j in range(W):
        if s[i][j] == -1:
            for k in range(prev, j):
                s[i][k] = n
            n = 0
            prev = j+1
        else:
            n += 1
    if n != 0:
        for k in range(prev, W):
            s[i][k] = n

for j in range(W):
    n = 0
    prev = 0
    for i in range(H):
        if s[i][j] == -1:
            for k in range(prev, i):
                s[k][j] += n
            n = 0
            prev = i+1
        else:
            n += 1
    if n != 0:
        for k in range(prev, H):
            s[k][j] += n

ans = np.amax(s) - 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def store_lamp(g, j, v):
    while j >= 0:
        if g[j] is not None:
            break
        g[j] = v
        j -= 1


def store_lamp_h(g, i, j, v):
    while i >= 0:
        if g[i][j] is not None:
            break
        g[i][j] = v
        i -= 1

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

hg = [[None] * w for _ in range(h)]
wg = [[None] * w for _ in range(h)]

for _ in range(h):
    s.append(input())

for i in range(h):
    pre = 0
    for j in range(w):
        if s[i][j] == '#':
            hg[i][j] = 0
            if pre != 0:
                store_lamp(hg[i], j-1, pre)
            pre = 0
        else:
            pre += 1

    if pre != 0:
        store_lamp(hg[i], w-1, pre)

for j in range(w):
    pre = 0
    for i in range(h):
        if s[i][j] == '#':
            wg[i][j] = 0
            if pre != 0:
                store_lamp_h(wg, i-1, j, pre)
            pre = 0
        else:
            pre += 1

    if pre != 0:
        store_lamp_h(wg, h-1, j, pre)

l = 0
for hh, wh in zip(hg, wg):
    for hw, ww in zip(hh, wh):
        l = max(l, hw+ww)

print(l-1)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int, input().split()))
S = [[0 if s=='#' else 1 for s in input()] for _ in range(H)] #S[h][w]

SH = [[0]*W for _ in range(H)]
SH_ = [[0]*W for _ in range(H)]

SV = [[0]*W for _ in range(H)]
SV_ = [[0]*W for _ in range(H)]

#horizontal
for h in range(H):
  SH[h][0] = S[h][0]
  for w in range(1,W):
    if S[h][w]:
      SH[h][w] = SH[h][w-1] + 1
  
  SH_[h][-1] = S[h][-1]
  for w in range(W-1)[::-1]:
    if S[h][w]:
      SH_[h][w] = SH_[h][w+1] + 1
  

#vertical
for w in range(W):
  SV[0][w] = S[0][w]
  for h in range(1,H):
    if S[h][w]:
      SV[h][w] = SV[h-1][w] + 1
  
  SV_[-1][w] = S[-1][w]
  for h in range(H-1)[::-1]:
    if S[h][w]:
      SV_[h][w] = SV_[h+1][w] + 1

#print(SH + SH_)
#print(SV + SV_)

ans = 0
for h in range(H):
  for w in range(W):
    ans = max(ans, SH[h][w] + SH_[h][w] + SV[h][w] + SV_[h][w] -3)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
H, W = map(int, input().split())
s = [input() for i in range(H)]

def length(index, block_idx, full_length):
    if len(block_idx) == 0:
        return full_length
    idx = bisect_left(block_idx, index)
    if idx == len(block_idx):
        return full_length - index
    return block_idx[idx] - index

rows = []

for i in range(H):
    row = [0 for k in range(W)]
    block_idx = []
    for k in range(len(s[i])):
        if s[i][k] == "#":
            block_idx.append(k)

    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                continue
            else:
                l = length(0, block_idx, W)
                row[j] = l
        else:
            if s[i][j] == "#":
                continue
            else:
                if s[i][j-1] != "#":
                    row[j] = row[j-1]
                else:
                    l = length(j, block_idx, W)
                    row[j] = l
    rows.append(row)

columns = []

for i in range(W):
    column = [0 for k in range(H)]

    _s = ""
    block_idx = []
    for k in range(H):
        _s += s[k][i]
        if s[k][i] == "#":
            block_idx.append(k)

    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                continue
            else:
                l = length(0, block_idx, H)
                column[j] = l
        else:
            if _s[j] == "#":
                continue
            else:
                if _s[j - 1] != "#":
                    column[j] = column[j-1]
                else:
                    l = length(j, block_idx, H)
                    column[j] = l
    columns.append(column)

res = []
max_score = 0
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        score = r + c - 1
        if max_score < score:
            max_score = score
print(max_score)

Submission status: Time Limit Exceeded

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

l = [0]*(w*h)
r = [0]*(w*h)
u = [0]*(w*h)
d = [0]*(w*h)

for i in range(h):
  for j in range(w):
    if s[i][j] == "#":
      l[i*w+j] = 0
      continue
    if j == 0:
      l[i*w+j] = 1
    else:
      l[i*w+j] = l[i*w+j-1] + 1
      
for i in range(h):
  for j in range(w):
    if s[i][(w-1)-j] == "#":
      r[i*w+(w-1)-j] = 0
    elif j == 0:
      r[i*w+(w-1)-j] = 1
    else:
      r[i*w+(w-1)-j] = r[i*w+(w-j)] + 1


for j in range(w):
  for i in range(h):
    if s[i][j] == "#":
      u[i*w+j] = 0
    elif i == 0:
      u[i*w+j] = 1
    else:
      u[i*w+j] = u[(i-1)*w+j] + 1

for j in range(w):
  for i in range(h):
    if s[(h-1)-i][j] == "#":
      d[((h-1)-i)*w+j] = 0
    elif i == 0:
      d[((h-1)-i)*w+j] = 1
    else:
      d[((h-1)-i)*w+j] = d[(h-i)*w+j] + 1

m = 3
for i in range(h):
  for j in range(w):
    m = max(m, l[i*w+j] + r[i*w+j] + u[i*w+j] + d[i*w+j]) 
print(m-3)

#print(d)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
L = []
for i in range(H):
	s = list(input())
	l = []
	count = 0
	for j in range(W):
		if s[j] == '#':
			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 j in range(H):
		if L[j][i] == 0:
			for k in range(count):
				L[j - k - 1][i] += count
			count = 0
		else:
			count += 1
	for k in range(count):
		L[H - k - 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:
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)

a = np.zeros((h,w), dtype=np.int)
#print(yoko)
b = np.zeros((h,w), dtype=np.int)
for i in range(h):
    for j in range(w):
        if grid[i][j]=='#':
            b[i][j] = 0
        else:
            b[i][j] = 1

for i in range(h):
    temp = 0
    for j in range(w):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

for i in range(h):
    temp = 0
    for j in range(w-1,-1,-1):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h-1,-1,-1):
        temp = (temp + 1)*b[i][j]
        a[i][j] += temp

answer=3
for i in range(h):
    for j in range(w):
        answer=max(a[i][j],answer)
#print(a)
print(answer-3)

Submission status: Time Limit Exceeded

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

m = []
for i in range(H):
    m.append(list(input()))

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

total = [[0] * W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if m[h][w] == "#":
            left[h][w] = 0
            up[h][w] = 0
            continue

        if w > 0:
            left[h][w] = left[h][w-1] + 1
        else:
            left[h][w] = 1

        if h > 0:
            up[h][w] = up[h-1][w] + 1
        else:
            up[h][w] = 1


for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if m[h][w] == "#":
            right[h][w] = 0
            down[h][w] = 0
            continue

        if w < W - 1:
            right[h][w] = right[h][w+1] + 1
        else:
            right[h][w] = 1

        if h < H - 1:
            down[h][w] = down[h+1][w] + 1
        else:
            down[h][w] = 1


for h in range(H):
    for w in range(W):
        total[h][w] = left[h][w] + right[h][w] + up[h][w] + down[h][w]
        total[h][w] -= 3

maxVal = max([max(row)for row in total])
print(maxVal)

Submission status: Time Limit Exceeded

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


def solve(H: int, W: int, S: "List[str]"):
    from collections import deque

    q = deque()
    ans = 0
    for i in range(H):
        for j in range(W):
            if(S[i][j] == '.'):
                q.append([i,j])

    while(len(q)):
        x,y = q.pop()
        t = 1
        
        # 上
        s = 1
        while(0 <= x-s < H and 0 <= y < W and S[x-s][y] == '.'):
            t += 1
            s += 1

        # 下
        s = 1
        while(0 <= x+s < H and 0 <= y < W and S[x+s][y] == '.'):
            t += 1
            s += 1

        # 左
        s = 1
        while(0 <= x < H and 0 <= y-s < W and S[x][y-s] == '.'):
            t += 1
            s += 1

        # 右
        s = 1
        while(0 <= x < H and 0 <= y+s < W and S[x][y+s] == '.'):
            t += 1
            s += 1

        ans = max(ans, t)

    print(ans)

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    S = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, S)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr
import itertools as it
import collections as col
import heapq as hq
import sys
sys.setrecursionlimit(10**9)

"""
N=int(input())
W=list(map(int, input().split()))
ans=10**100
for T in range(1,N):
        S1=sum(W[:T])
        S2=sum(W[T:])
        ans = min(ans, abs(S1-S2))
print(ans)
"""
"""
P,Q,R=map(int, input().split())
print(min([P+Q, P+R, Q+R]))
"""
"""
MOD=1000000007
N,M=map(int, input().split())
A=set()
for i in range(M):
        A.add(int(input()))

dp=dict()
dp[0]=1
dp[1]=0 if 1 in A else 1
for i in range(2, N+1):
        if i in A: dp[i] = 0
        else:
                m1=0 if (i-1) in A else dp[i-1]
                m2=0 if (i-2) in A else dp[i-2]
                dp[i]=(m1+m2) % MOD
print(dp[N])
"""
H,W=map(int, input().split())
S=[]
for i in range(H):
        s=input()
        S.append(list(s))
SWR=[]
for i in range(H):
        SWR.append([0 if S[i][0] == "#" else 1])
        for j in range(1,W):
                if S[i][j] == "#": SWR[i].append(0)
                else: SWR[i].append(SWR[i][j-1] + 1)

SWL=[]
for i in range(H):
        SWL.append([0 if S[i][W-1] == "#" else 1])
        for j in range(1,W):
                if S[i][W-j-1] == "#": SWL[i].append(0)
                else: SWL[i].append(SWL[i][j-1] + 1)
        SWL[i].reverse()

SHB=[[]]
for j in range(W):
        SHB[0].append(0 if S[0][j] == "#" else 1)
for i in range(1,H):
        SHB.append([])
        for j in range(W):
                if S[i][j] == "#": SHB[i].append(0)
                else: SHB[i].append(SHB[i-1][j] + 1)

SHT=[[]]
for j in range(W):
        SHT[0].append(0 if S[H-1][j] == "#" else 1)
for i in range(1,H):
        SHT.append([])
        for j in range(W):
                if S[H-i-1][j] == "#": SHT[i].append(0)
                else: SHT[i].append(SHT[i-1][j] + 1)
SHT.reverse()

ans=0
for i in range(H):
        for j in range(W):
                x=SWR[i][j] + SWL[i][j] + SHB[i][j] + SHT[i][j] - 3
                ans=max(ans,x)
print(ans)

Submission status: Time Limit Exceeded

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



h,w = words(int)
wq = [0] * w

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] == '#':
            wq[j] = 0
            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
            if not wq[x] == 0:
                vplus = wq[x]
            else:
                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)
            wq[x] = vplus
        j = j+k
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(H):
  w = input()
  for j in range(W):
    O[i][j] = w[j]

for i in range(H):
  w = O[i]
  w.append('e')
  j = 0
  while j < W:
    if w[j] == '#':
      j += 1
      continue
    else:
      start = j
      while w[j] == '.' and w[j+1] == '.':
        j += 1
      for k in range(start, j+1):
          S[i][k] = j - start + 1
      j += 1

res = -10000      
      
for i in range(W):
  w = [o[i] for o in O]
  w.append('e')
  j = 0
  while j < H:
    if w[j] == '#':
      j += 1
      continue
    else:
      start = j
      while w[j] == '.' and w[j+1] == '.':
        j += 1
      for k in range(start, j+1):
          C[k][i] = j - start + 1
          res = max(res, C[k][i] + S[k][i] - 1)
      j += 1

print (res)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().split()))
Hs = [[0] * W for i in range(H)]
Vs = [[0] * W for i in range(H)]

Ss = [0] * H
for i in range(H):
    Ss[i] = input()

# 横
for i in range(H):
    s = 0
    e = 0
    c = 0
    for k in range(W):
        if Ss[i][k] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Hs[i][s + m] = c
            s = e + 1
            c = 0
    e = W
    for m in range(e - s):
        Hs[i][s + m] = c
# 縦
for i in range(W):
    s = 0
    e = 0
    c = 0
    for k in range(H):
        if Ss[k][i] == ".":
            c += 1
        else:
            e = k
            for m in range(e - s):
                Vs[s + m][i] = c
            s = e + 1
            c = 0
    e = H
    for m in range(e - s):
        Vs[s + m][i] = c

maxv = 0
for i in range(H):
    for k in range(W):
        t = Hs[i][k] + Vs[i][k] - 1
        if t > maxv:
            maxv = t
print(maxv)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W = map(int,input().split())
# H,W = 2000,2000

S = np.zeros((H,W),dtype=np.int)
for h in range(H):
    l = input()
    for w in range(W):
        if l[w]=="#":
            S[h,w] = 0
        else:
            S[h,w] = 1

Sh = np.zeros((H,W),dtype=np.int)


for h in range(H):
    se = []
    cnt = 0
    for w,val in enumerate(S[h]):
        if val == 1:
            cnt += 1
            se.append(w)
        else:
            for ww in se:
                Sh[h,ww] = cnt
            cnt = 0
            se = []
    for ww in se:
        Sh[h,ww] = cnt

Sw = np.zeros((H,W),dtype=np.int)

for w in range(W):
    se = []
    cnt = 0
    for h,val in enumerate(S[:,w]):
        if val == 1:
            cnt += 1
            se.append(h)
        else:
            for hh in se:
                Sw[hh,w] = cnt
            cnt = 0
            se = []
    for hh in se:
        Sw[hh,w] = cnt


print(max((Sh+Sw).max()-1,0))