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 = (int(i) for i in input().split())
#e = [[i for i in input().split()] for i in range(H)]
e = []
for x in range(H):
    e.append(list(input()))

maxcount = 1
for i in range(H):
    for j in range(W):
        #print("start", i, j)
        count = 1
        if e[i][j] == "#":
            continue
        for k in range(i+1, H):
            #print(e[k][j], k, j)
            if e[k][j] == "#":
                #print(k, j)
                break
            else:
                count +=1
        #print("1 ", count)
        for l in range(1, i+1):
            #print(e[i-l][j], i-l, j)
            if e[i-l][j] == "#":
                break
            else:
                count += 1
        #print("2 ", count)
        for m in range(j+1, W):
            if e[i][m] == "#":
                break
            else:
                count +=1
        #print("3 ",count)
        for n in range(1, j+1):
            if e[i][j-n] == "#":
                break
            else:
                count +=1
        if maxcount < count:
            maxcount = count
        #print(count)
print(maxcount)

Submission status: Time Limit Exceeded

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

def counter(x, y):
    count = 1
    h1 = x - 1
    while h1 >= 0 and s[h1][y] == ".":
        count += 1
        h1 -= 1
    
    h2 = x + 1
    while h2 < H and s[h2][y] == ".":
        count += 1
        h2 += 1
    
    w1 = y -1
    while w1 >= 0 and s[x][w1] == ".":
        count += 1
        w1 -= 1
    
    w2 = y + 1
    while w2 < W and s[x][w2] == ".":
        count += 1
        w2 += 1
    
    return count

c = []
for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            c.append(counter(i, j))

print(max(c))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import heapq
import math
import sys


H, W = [int(a) for a in input().split()]
board_val = [[0 for i in range(W+2)] for j in range(H+2)]
board_state = [[True for i in range(W+2)] for j in range(H+2)]
for h in range(H+2):
    if h == 0 or h == H+1:
        board_state[h] = [False for i in range(W+2)]
        continue
    row_state = board_state[h]
    row_state[0] = row_state[W+1] = False
    s = input()
    for w_, c in enumerate(s):
        w = w_ + 1
        if c == '.':
            row_state[w] = True
        else:
            assert c == '#'
            row_state[w] = False

for h in range(H+2):
    val = 0
    begin = None
    for w in range(W+2):
        ok = board_state[h][w]
        if ok:
            if begin is None:
                begin = w
            val += 1
        else:
            if begin is None:
                continue
            for nuri in range(begin, w):
                board_val[h][nuri] += val
            val = 0
            begin = None
    
for w in range(W+2):
    val = 0
    begin = None
    for h in range(H+2):
        ok = board_state[h][w]
        if ok:
            if begin is None:
                begin = h
            val += 1
        else:
            if begin is None:
                continue
            for nuri in range(begin, h):
                board_val[nuri][w] += val
            val = 0
            begin = None

def mat_to_str(mat):
    return '\n'.join([', '.join([str(e) for e in row]) for row in mat])

print(max([max(row) for row in board_val])-1)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left,bisect_right
inf=float('inf')
mod = 10**9+7
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H, W = MI()
    S = [ST() for _ in range(H)]
    cumsum1 = [[] for _ in range(H)]
    cumsum2 = [[] for _ in range(W)]
    
    for h in range(H):
        for w in range(W):
            if w == 0:
                cumsum1[h].append(int(S[h][w] == "#"))
            else:
                cumsum1[h].append(cumsum1[h][-1] + (S[h][w] == "#"))
            if h == 0:
                cumsum2[w].append(int(S[h][w] == "#"))
            else:
                cumsum2[w].append(cumsum2[w][-1] + (S[h][w] == "#"))
    """print(*cumsum1,sep="\n")"""
    #print(*cumsum2,sep="\n") 
    ans=0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            else:
                c1 = cumsum1[h][w]
                c2 = cumsum2[w][h]
                #print((h, w), cumsum1[h], cumsum2[w], sep="\n")
                b1,b2,b3,b4 = bisect_right(cumsum1[h], c1) ,bisect_left(cumsum1[h], c1) , bisect_right(cumsum2[w], c2) , bisect_left(cumsum2[w], c2)
                num = b1 - b2 + b3 - b4 -3 +(b2==0) + (b4 == 0) 
                #num = bisect_right(cumsum1[h], c1) - bisect_left(cumsum1[h], c1) + bisect_right(cumsum2[w], c2) - bisect_left(cumsum2[w], c2)-1 + (h==0)+(w==0)
                #print(num,b1,b2,b3,b4)
                ans=max(ans,num)
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

S_t = list(map(list, zip(*S)))

S_h = [[] for i in range(H)]
S_w = [[] for i in range(W)]

for x in range(W):
    for y in range(H):
        if S[y][x] == '#':
            S_h[y].append(x)
            S_w[x].append(y)

ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == '.':
            c = 1
            if len(S_w[x]) == 0:
                c += H-1
            else:
                i = bisect_left(S_w[x],y)
                if i == 0:
                    c += S_w[x][0]-1
                elif i == len(S_w[x]):
                    c += H-S_w[x][-1]-2
                else:
                    c += S_w[x][i]-S_w[x][i-1]-2
            if len(S_h[y]) == 0:
                c += W-1
            else:
                i = bisect_left(S_h[y],x)
                if i == 0:
                    c += S_h[y][0]-1
                elif i == len(S_h[y]):
                    c += W-S_h[y][-1]-2
                else:
                    c += S_h[y][i]-S_h[y][i-1]-2
            ans = max(ans,c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 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 input()
from bisect import bisect_left

def main():
    H, W = LI()
    hs = [[-1] for _ in range(H)]
    ws = [[-1] for _ in range(W)]
    for h in range(H):
        s = SI()
        for w, ss in enumerate(s):
            if ss == '#':
                hs[h].append(w)
                ws[w].append(h)
    for h in range(H):
        hs[h].append(W)
    for w in range(W):
        ws[w].append(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            i = bisect_left(hs[h], w)
            j = bisect_left(ws[w], h)
            ans = max(ans, hs[h][i] - hs[h][i - 1] + ws[w][j] - ws[w][j - 1] - 3)
    return ans

print(main())

Submission status: Time Limit Exceeded

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


def dfs(h, w):
    ans = 0
    for hp in range(h - 1, 0 - 1, -1):
        if S[hp][w] == '.':
            ans += 1
        else:
            break
    for wp in range(w - 1, 0 - 1, -1):
        if S[h][wp] == '.':
            ans += 1
        else:
            break
    for hp in range(h + 1, H, 1):
        if S[hp][w] == '.':
            ans += 1
        else:
            break
    for wp in range(w + 1, W, 1):
        if S[h][wp] == '.':
            ans += 1
        else:
            break
    return ans + 1


ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            ans = max(dfs(h, w), ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=list(map(int,input().strip().split(' ')))
grid=[]
for _ in range(H):
    grid+=[input()]

block_h=[]
for i in range(H):
    temp=[-1]
    for j in range(W):
        if grid[i][j]=="#":
            temp+=[j]
    temp+=[W]
    block_h+=[temp]

block_c=[]
for j in range(W):
    temp=[-1]
    for i in range(H):
        if grid[i][j]=="#":
            temp+=[i]
    temp+=[H]
    block_c+=[temp]

#print(block_h)
#print(block_c)
import bisect
MAX=0
for i in range(H):
    for j in range(W):
        #print(i,j)
        ans=0
        if grid[i][j]==".":
            post=bisect.bisect_right(block_c[j],i)
            #print(post)
            a1=block_c[j][post-1]
            a2=block_c[j][post]
            ans+=a2-a1-1

            post=bisect.bisect_right(block_h[i],j)
            #print(post)
            a1=block_h[i][post-1]
            a2=block_h[i][post]
            ans+=a2-a1-1            
            MAX=max(MAX,ans)
print(MAX-1)

Submission status: Time Limit Exceeded

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

def readInts():
  return [int(s) for s in input().split(" ")]

class UnionFind:
  def __init__(self, N):
    self.elems = list(range(N))
    self.ranks = [1] * N

  def root(self, i):
    a = i
    while self.elems[i] != i:
      i = self.elems[i]
    self.elems[a] = i
    return i

  def rank(self, i):
    return self.ranks[self.root(i)]

  def unite(self, i, j):
    rootI = self.root(i)
    rootJ = self.root(j)
    if rootI == rootJ:
      return

    if self.rank(i) > self.rank(j):
      self.elems[rootJ] = rootI
      self.ranks[rootI] += self.ranks[rootJ]
    else:
      self.elems[rootI] = rootJ
      self.ranks[rootJ] += self.ranks[rootI]

def main():
  H, W = readInts()
  S = [input() for _ in range(H)]

  ufW = [UnionFind(W) for _ in range(H)]
  ufH = [UnionFind(H) for _ in range(W)]

  for h in range(H):
    for w in range(W-1):
      if S[h][w] != '#' and S[h][w+1] != '#':
        ufW[h].unite(w, w+1)

  for w in range(W):
    for h in range(H-1):
      if S[h][w] != '#' and S[h+1][w] != '#':
        ufH[w].unite(h, h+1)

  ans = 0
  for h in range(H):
    for w in range(W):
      if S[h][w] != '#':
        ans = max(ans, ufW[h].rank(w) + ufH[w].rank(h) - 1)

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import sys

input = sys.stdin.readline

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

row_blocks = []
for r in range(H):
    t = [-1]
    for c in range(W):
        if s[r][c] == '#':
            t.append(c)
    t.append(W)
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = [-1]
    for r in range(H):
        if s[r][c] == '#':
            t.append(r)
    t.append(H)
    col_blocks.append(t)
# print(col_blocks)

rr = [[None] * W for _ in range(H)]
cc = [[None] * W for _ in range(H)]

for r in range(H):
    for c in range(W):
        ri = bisect_left(row_blocks[r], c)
        rr[r][c] = (row_blocks[r][ri] - 1) - row_blocks[r][ri - 1]
        ci = bisect_left(col_blocks[c], r)
        cc[r][c] = (col_blocks[c][ci] - 1) - col_blocks[c][ci - 1]

ans = 0
for r in range(H):
    for c in range(W):
        t = rr[r][c] + cc[r][c] - 1
        ans = max(ans, t)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# from collections import Counter, deque, defaultdict
# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
# N = int(input())
# A,B,C = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]

H, W = [int(x) for x in input().split()]
S = []
for h in range(H):
    S.append(input())

Th = [[0] * W for _ in range(H)]
Tw = [[0] * W for _ in range(H)]

for h in range(H):
    cnt = 0
    st = 0
    for w in range(W):
        if S[h][w] == "#":
            for i in range(st, w):
                Tw[h][i] = cnt
            st = w + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, W):
        Tw[h][i] = cnt

for w in range(W):
    cnt = 0
    st = 0
    for h in range(H):
        if S[h][w] == "#":
            for i in range(st, h):
                Th[i][w] = cnt
            st = h + 1
            cnt = 0
        else:
            cnt += 1
    for i in range(st, H):
        Th[i][w] = cnt

ALL = []
for w in range(W):
    for h in range(H):
        ALL.append(Tw[h][w] + Th[h][w])

print(max(ALL) - 1)

Submission status: Time Limit Exceeded

Solution code:


def read_input():
    h, w = map(int, input().split())

    board = []
    for i in range(h):
        board.append([c for c in input()])

    return h, w, board


def submit():
    h, w, board = read_input()

    hcount = {}
    wcount = {}

    for i in range(h):
        stock = []
        count = 0
        for j in range(w):
            if board[i][j] == '#': # カウントをセット
                for s in stock:
                    hcount[s] = count
                stock = []
                count = 0
            else: # ストック
                stock.append((i, j))
                count += 1

        if stock:
            for s in stock:
                hcount[s] = count

    for i in range(w):
        stock = []
        count = 0
        for j in range(h):
            if board[j][i] == '#':  # カウントをセット
                for s in stock:
                    wcount[s] = count
                stock = []
                count = 0
            else:  # ストック
                stock.append((j, i))
                count += 1

        if stock:
            for s in stock:
                wcount[s] = count


    max_lit = 0
    for hk, hv in hcount.items():
        wv = wcount[hk]

        if hv + wv - 1 > max_lit:
            max_lit = hv + wv - 1

    print(max_lit)







if __name__ == '__main__':
    submit()

Submission status: Time Limit Exceeded

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

rows = []

for i in range(H):
    row = []
    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                row.append(0)
            else:
                idx = s[i].find("#")
                if idx == -1:
                    idx = W
                row.append(idx)
        else:
            if s[i][j] == "#":
                row.append(0)
            else:
                if s[i][j-1] != "#":
                    row.append(row[len(row)-1])
                else:
                    idx = s[i].find("#", j)
                    if idx == -1:
                        idx = W
                    row.append(idx - j)
    rows.append(row)

columns = []

for i in range(W):
    column = []
    _s = ""
    for k in range(H):
        _s += s[k][i]
    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                column.append(0)
            else:
                idx = _s.find("#")
                if idx == -1:
                    idx = H
                column.append(idx)
        else:
            if _s[j] == "#":
                column.append(0)
            else:
                if _s[j - 1] != "#":
                    column.append(column[len(column) - 1])
                else:
                    idx = _s.find("#", j)
                    if idx == -1:
                        idx = H
                    column.append(idx - j)
    columns.append(column)

res = []
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        res.append(r+c-1)
print(max(res))

Submission status: Time Limit Exceeded

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


tab_h = [[0] * W for _ in range(H)]
tab_v = [[0] * W for _ in range(H)]

for i in range(H):
    memo = [0] * W
    tmp = 0
    for j in range(W):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[j] = tmp
    tmp = 0
    for j in range(W):
        if tmp == 0 and memo[W - 1 - j] > 0:
            tmp = memo[W - 1 - j]
        elif memo[W - 1 - j] == 0:
            tmp = 0
        tab_h[i][W - 1 - j] = tmp

for j in range(W):
    memo = [0] * H
    tmp = 0
    for i in range(H):
        if S[i][j] == '.':
            tmp += 1
        else:
            tmp = 0
        memo[i] = tmp
    tmp = 0
    for i in range(H):
        if tmp == 0 and memo[H - 1 - i] > 0:
            tmp = memo[H - 1 - i]
        elif memo[H - 1 - i] == 0:
            tmp = 0
        tab_v[H - 1 - i][j] = tmp

# for i in range(H): print("#", tab_h[i])
# for i in range(H): print("#", tab_v[i])

ans = 1
for i in range(H):
    for j in range(W):
        ans_tmp = tab_h[i][j] + tab_v[i][j] - 1
        if ans < ans_tmp:
            ans = ans_tmp

print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        else:
            cnt = 1 # 光の数 自分も含む

            flg = True
            k = 1
            while flg:
                if i-k < 0:
                    flg = False
                    break
                else:
                    if S[i-k][j] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if j-k < 0:
                    flg = False
                    break
                else:
                    if S[i][j-k] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if i+k >= H:
                    flg = False
                    break
                else:
                    if S[i+k][j] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            flg = True
            k = 1
            while flg:
                if j+k >= W:
                    flg = False
                    break
                else:
                    if S[i][j+k] == '#':
                        flg = False
                        break
                    else:
                        cnt += 1
                k += 1

            ans = max(cnt, ans)

print(ans)

Submission status: Time Limit Exceeded

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

A = [[0] * W for i in range(H)]


for i in range(H):
  work = 0
  fj = 0
  for j in range(W+1):
    if j == W or S[i][j] == '#':
      for k in range(fj,j):
        A[i][k] += work
      work = 0
      fj = j + 1
    else:
      work += 1
      
for i in range(W):
  work = 0
  fj = 0
  for j in range(H+1):
    if j == H or S[j][i] == '#':
      for k in range(fj,j):
        A[k][i] += work
      work = 0
      fj = j + 1
    else:
      work += 1

ans = 0
for i in range(H):
  #print(A[i])
  ans = max(ans, max(A[i]))
  
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = [0 for i in range(n)]
for i in range(n):
  a[i] = input()
num = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
  for j in range(m):
    if a[i][j] == ".":
      num[i][j] += 1
      # 下
      i_2 = i+1
      j_2 = j
      if i_2 < n:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 += 1
          if i_2 >= n:
            break
      # 上
      i_2 = i-1
      j_2 = j
      if 0 <= i_2:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          i_2 -= 1
          if 0 > i_2:
            break
      # 上
      i_2 = i
      j_2 = j-1
      if 0 <= j_2:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 -= 1
          if 0 > j_2:
            break
      # 下
      i_2 = i
      j_2 = j+1
      if j_2 < m:
        while a[i_2][j_2] == ".":
          num[i][j] += 1
          j_2 += 1
          if j_2 >= m:
            break
print(max([max(i) for i in num]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

result = 0
#memo = {}


def terasu(x, y, d):
    #print(x, y, h, w)
    if y < 0 or x < 0 or y >= h or x >= w:
        return 0
    # if (x, y) in memo.keys():
    #    return 0
    if s[y][x] == "#":
        return 0
    #memo[(x, y)] = True
    if d == "f":
        return 1 + terasu(x + 1, y, "e") + terasu(x, y - 1, "s") + terasu(x, y+1, "n") + terasu(x-1, y, "w")
    elif d == "e":
        return 1 + terasu(x + 1, y, "e")
    elif d == "s":
        return 1 + terasu(x, y - 1, "s")
    elif d == "n":
        return 1 + terasu(x, y+1, "n")
    elif d == "w":
        return 1 + terasu(x-1, y, "w")


for y in range(h):
    for x in range(w):
        result = max(result, terasu(x, y, "f"))
print(result)

Submission status: Time Limit Exceeded

Solution code:
def get_lighted_tiles(h, w):
    res = 1
    for i in range(h-1, 0-1, -1):
        if S[i][w] == '.':
            res += 1
        else:
            break
    for i in range(h+1, H):
        if S[i][w] == '.':
            res += 1
        else:
            break
    for j in range(w-1, -1, -1):
        if S[h][j] == '.':
            res += 1
        else:
            break
    for j in range(w+1, W):
        if S[h][j] == '.':
            res += 1
        else:
            break
    return res
  

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

plains = [[i, j] for i in range(H) for j in range(W) if S[i][j]=='.']
print(max([get_lighted_tiles(*p) for p in plains]))

Submission status: Time Limit Exceeded

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

for n in range(H):
  G = G + [input()]
  
L = [[0 for w in range(W)] for h in range(H)]
R = [[0 for w in range(W)] for h in range(H)]
U = [[0 for w in range(W)] for h in range(H)]
D = [[0 for w in range(W)] for h in range(H)]

for i in range(H):
  for j in range(1,W):
    if G[i][j]=='#' or G[i][j-1]=='#':
      L[i][j] = 0
    else:
      L[i][j] = L[i][j-1]+1
        
    if G[i][W-1-j]=='#' or G[i][W-j]=='#':
      R[i][W-1-j] = 0
    else:
      R[i][W-1-j] = R[i][W-j]+1
  
for i in range(1,H):
  for j in range(W):
    if G[i][j]=='#' or G[i-1][j]=='#':
      U[i][j] = 0
    else:
      U[i][j] = U[i-1][j]+1
        
    if G[H-1-i][j]=='#' or G[H-i][j]=='#':
      D[H-1-i][j] = 0
    else:
      D[H-1-i][j] = D[H-i][j]+1

v = [0]*H
for i in range(H):
  v_ = [0]*W
  for j in range(W):
    if G[i][j]=='.':
      v_[j] = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
  v[i] = max(v_)
print(max(v))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc129/tasks/abc129_d

import itertools
from collections import Counter
from collections import defaultdict
import bisect
from heapq import heappush, heappop

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

    def down(i, j):
        val = 0
        pos = i - 1
        while pos >= 0:
            if grid[pos][j] != '#':
                val += 1
            else:
                break
            pos -= 1

        return val

    def up(i, j):
        val = 0
        pos = i + 1
        while pos < H:
            if grid[pos][j] != '#':
                val += 1
            else:
                break
            pos += 1

        return val

    def left(i, j):
        val = 0
        pos = j - 1
        while pos >= 0:
            if grid[i][pos] != '#':
                val += 1
            else:
                break
            pos -= 1

        return val

    def right(i, j):
        val = 0
        pos = j + 1
        while pos < W:
            if grid[i][pos] != '#':
                val += 1
            else:
                break
            pos += 1

        return val

    def count(i, j):
        return 1 + down(i, j) + up(i, j) + right(i, j) + left(i, j)

    ans = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] != '#':
                ans = max(ans, count(h, w))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

rows = []

for i in range(H):
    row = []
    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                row.append(0)
            else:
                idx = s[i].find("#")
                if idx == -1:
                    idx = W
                row.append(idx)
        else:
            if s[i][j] == "#":
                row.append(0)
            else:
                if s[i][j-1] != "#":
                    row.append(row[len(row)-1])
                else:
                    idx = s[i].find("#", j)
                    if idx == -1:
                        idx = W
                    row.append(idx - j)
    rows.append(row)

columns = []

for i in range(W):
    column = []
    _s = ""
    for k in range(H):
        _s += s[k][i]
    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                column.append(0)
            else:
                idx = _s.find("#")
                if idx == -1:
                    idx = H
                column.append(idx)
        else:
            if _s[j] == "#":
                column.append(0)
            else:
                if _s[j - 1] != "#":
                    column.append(column[len(column) - 1])
                else:
                    idx = _s.find("#", j)
                    if idx == -1:
                        idx = H
                    column.append(idx - j)
    columns.append(column)

res = []
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        res.append(r+c-1)
print(max(res))

Submission status: Time Limit Exceeded

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

aa = []
for y in range(h):
    aa.append([0] * w)

ans = 0

for y in range(h):
    l = 0
    for x in range(w):
        if s[y][x] == '#':
            for i in range(l, x):
                aa[y][i] = x - l
            l = x + 1
    for i in range(l, w):
        aa[y][i] = w - l

for x in range(w):
    t = 0
    for y in range(h):
        if s[y][x] == '#':
            for i in range(t, y):
                aa[i][x] += y - t
                ans = max(ans, aa[i][x])
            t = y + 1
    for i in range(t, h):
        aa[i][x] += h - t
        ans = max(ans, aa[i][x])
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
import numpy
H,W = (int(x) for x in input().split())

S_arr_arr = [[1]*(W+2)]
for i in range(H):
    S_arr_arr.append([0 if s=="." else 1 for s in "#"+input()+"#"])
S_arr_arr.append([1]*(W+2))
W_arr_arr = [[0]*(W+2) for _ in range(H+2)]

S_arr_arr = numpy.array(S_arr_arr)
W_arr_arr = numpy.zeros_like(S_arr_arr)

for j in range(H+2):
    i_begin = 0
    for i in range(W+2):
        if S_arr_arr[j,i] == 1:
            for ix in range(i_begin+1, i):
                W_arr_arr[j,ix] += i-i_begin-1
            i_begin = i
for i in range(W+2):
    j_begin = 0
    for j in range(H+2):
        if S_arr_arr[j,i] == 1:
            for jx in range(j_begin+1, j):
                W_arr_arr[jx,i] += j-j_begin-1
            j_begin = j

max_ans = max([max(W_arr) for W_arr in W_arr_arr]) - 1

print(max_ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
h,w = map(int,input().split())
s = []
for i in range(h):
        a = [i for i in input().rstrip()]
        s.append(a)
x = [[[0,0,0,0]for i in range(w)] for j in range(h)]
for i in range(h):
        for j in range(w):
                if s[i][j] == "." and 0<j and s[i][j-1] == ".":
                        x[i][j][0] = x[i][j-1][0] +1

for i in range(h):
        for j in range(w-1,-1,-1):
                if s[i][j] == "." and w-1>j and s[i][j+1] == ".":
                        x[i][j][1] = x[i][j+1][1] +1

for i in range(w):
        for j in range(h-1,-1,-1):
                if s[j][i] == "." and h-1>j and s[j+1][i] == ".":
                        x[j][i][2] = x[j+1][i][2] +1

for i in range(w):
        for j in range(h):
                if s[j][i] == "." and 0<j and s[j-1][i] == ".":
                        x[j][i][3] = x[j-1][i][3] +1                   
ans = 0
for i in range(h):
        for j in range(w):
                if s[i][j] == ".":
                        ans = max(ans,sum(x[i][j])+1)

print(ans)