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 _ in range(H)]

total = 0

# h, w, [yoko, tate]
table = []
for h in range(H):
    table.append([])
    for w in range(W):
        table[h].append([0, 0])

# 横を数える
for h in range(H):
    # 行き
    for w in range(W):
        if S[h][w] == "#":
            continue

        if 0 < w:
            table[h][w][0] = table[h][w-1][0] + 1
        else:
            table[h][w][0] = 1

    # 帰り
    for w in reversed(range(W)):
        if S[h][w] == "#":
            continue

        if w == W-1:
            pass
        else:
            table[h][w][0] = max(table[h][w][0], table[h][w+1][0])


# 縦を数える
for w in range(W):
    # 行き
    for h in range(H):
        if S[h][w] == "#":
            continue

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

    # 帰り
    for h in reversed(range(H)):
        if S[h][w] == "#":
            continue

        if h == H-1:
            pass
        else:
            table[h][w][1] = max(table[h][w][1], table[h+1][w][1])
        total = max(total, sum(table[h][w]) - 1)

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        else:
            if j != 0:
                a[i].append(k)
                al[i].append(j-1)
                k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        else:
            if j != 0:
                b[i].append(k)
                bl[i].append(j-1)
                k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][bisect_left(al[i], j)]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
nl = lambda: list(map(int, input().split()))
s = lambda: input()

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

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


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

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

print(int(res))

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)
    else:
      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)
    else:
      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 numpy as np
from itertools import groupby
h, w = map(int,input().split())

maze=np.zeros((h,w),dtype=int)
dst_h = np.zeros((h,w),dtype=int)
dst_w = np.zeros((h,w),dtype=int)
h_max=0
w_max=0
for i in range(h):
  line = input()
  maze[i] = [0 if s =="." else 1 for s in line]
  dst_raw = [sum(1 for e in it) for _, it in groupby(maze[i], key=lambda x: x == 0)]
  pre = 1 if maze[i][0] == 0 else 0
  flag = pre
  count = 0
  
  for d in dst_raw:
    if flag:
      dst_h[i][count:count+d] = d
    else:
      dst_h[i][count:count+d] = 0
    flag = (flag+1)%2
    count += d
              
for i in range(w):
  dst_raw = [sum(1 for e in it) for _, it in groupby(maze[:,i], key=lambda x: x == 0)]
  pre = 1 if maze[:,i][0] == 0 else 0
  flag = pre
  count = 0
  
  for d in dst_raw:
    if flag:
      dst_w[:,i][count:count+d] = d
    else:
      dst_w[:,i][count:count+d] = 0
    flag = (flag+1)%2
    count += d
print(np.amax(dst_h+dst_w-1))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

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

R = [[] for i in range(H)]
for j in range(H):
    R[j].append(-1)
    for i in range(W):
        if S[j][i] == "#":
            R[j].append(i)
    R[j].append(W)

C = [[] for i in range(W)]
for j in range(W):
    C[j].append(-1)
    for i in range(H):
        if S[i][j] == "#":
            C[j].append(i)
    C[j].append(H)

ma = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue

        r = bisect_left(R[i], j)
        c = bisect_left(C[j], i)

        rr = R[i][r] - R[i][r - 1] - 1
        cc = C[j][c] - C[j][c - 1] - 1

        ma = max(ma, rr + cc - 1)

print(ma)

Submission status: Time Limit Exceeded

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

ans,v = 0,[0 for i in range(W)]
for i in range(1,W+1):
    k = 1
    while S[k][i] == '.':
        k += 1
    v[i-1] = k - 1

for i in range(1,H+1):
    dot = 1
    while S[i][dot] == '.':
            dot += 1
    dot -= 1
    for j in range(1,W+1):
        if S[i][j] == '#':
            k = j+1
            while S[i][k] == '.':
                k += 1
            dot = k - j - 1

            k = i+1
            while S[k][j] == '.':
                k += 1
            v[j-1] = k - i - 1 
        else:
            if ans < dot + v[j-1]:    ans = dot + v[j-1]
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys
from pprint import pprint

WARU = 1000000007

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

def key(h,w):
    return "{}:{}".format(h,w)

ans = [] # right,under
for h in range(H):
    line = [ [0,0] for x in range(W) ]
    ans.append(line)

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            ans[h][w] = [0,0]
            continue
        right = 0
        under = 0
        if w == 0 or ans[h][w-1][0] == 0:
            for i in range(w + 1,W):
                if S[h][i] == "#":
                    break
                right += 1
        else:
            right = ans[h][w-1][0]
        if h == 0 or ans[h-1][w][1] == 0:
            for i in range(h+1,H):
                if S[i][w] == "#":
                    break
                under += 1
        else:
            under = ans[h-1][w][1]
        ans[h][w] = [right,under]

max_mass = 0
max_count = 0

for h in range(H):
    for w in range(W):
        if max_count < ans[h][w][0] + ans[h][w][1]:
            max_count = ans[h][w][0] + ans[h][w][1]
            max_mass = ans[h][w]

print(max_count + 1)

Submission status: Time Limit Exceeded

Solution code:
import bisect

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
dh = {}
for i in range(h):
    dh[i] = []
    for j in range(w):
        if s[i][j] == "#":
            dh[i].append(j)
dw = {}
for i in range(w):
    dw[i] = []
    for j in range(h):
        if s[j][i] == "#":
            dw[i].append(j)
ans = 0
for i in range(h):
    a = dh[i]
    for j in range(w):
        if s[i][j] == "#":
            continue
        b = dw[j]
        c = bisect.bisect_left(a, j)
        if not a:
            wl = w
        else:
            if c == 0:
                wl = a[0]
            elif c == len(a):
                wl = w - a[-1] - 1
            else:
                wl = a[c] - a[c - 1] - 1
        d = bisect.bisect_left(b, i)
        if not b:
            hl = h
        else:
            if d == 0:
                hl = b[0]
            elif d == len(b):
                hl = h - b[-1] - 1
            else:
                hl = b[d] - b[d - 1] - 1
        ans = max(ans, wl + hl - 1)
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(i,j,k)
        if k + h <= ans:
            j = j + k
            continue
        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:
import sys

input = sys.stdin.readline

H, W = map(int, input().split())
L = []

def checki(ii, jj):
    cnt = 0
    i, j = ii, jj
    while i >= 0 and i < H and L[i][j] == ".":
        cnt += 1
        i -= 1
    i, j = ii, jj
    while i >= 0 and i < H and L[i][j] == ".":
        cnt += 1
        i += 1
    i, j = ii, jj
    while j >= 0 and j < W and L[i][j] == ".":
        cnt += 1
        j -= 1
    i, j = ii, jj
    while j >= 0 and j < W and L[i][j] == ".":
        cnt += 1
        j += 1
    return cnt - 3

for i in range(H):
    L.append(list(input()))

ans = -1
for i in range(H):
    for j in range(W):
        if L[i][j] == "#":
            continue
        numi = checki(i, j)
        if ans < numi:
            ans = numi
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())

s=[input() for i in range(h)]

# def ok(i,j,houkou, count):
#     if i==h or j==w:
#         return count
#     elif s[i][j]=='#':
#         return count
#     elif houkou=='yoko':
#         return ok(i,j+1,houkou,count+1)
#     else:
#         return ok(i+1,j,houkou,count+1)

yoko=[[0 for i in range(w)] for j in range(h)]
tate=[[0 for i in range(w)] for j in range(h)]

count=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#':
            for k in range(count):
                yoko[i][j-k-1]=count
            count=0
    if count>0:
        for k in range(count):
            yoko[i][j-k]=count
        count=0
# print(yoko)


for j in range(w):
    for i in range(h):
        if s[i][j]=='.':
            count+=1
        if s[i][j]=='#':
            for k in range(count):
                tate[i-k-1][j]=count
            count=0
    if count>0:
        for k in range(count):
            tate[i-k][j]=count
        count=0

# print(tate)

ans=0
for i in range(h):
    for j in range(w):
        if ans<yoko[i][j]+tate[i][j]-1:
            ans=yoko[i][j]+tate[i][j]-1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

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

    return res


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

row_wise = np.apply_along_axis(f, 0, grid)
col_wise = np.apply_along_axis(f, 1, grid)

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

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

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
list=[]
for i in range(H):
    s=input()
    list.append(s)
max=0
for i in range(H):
    for j in range(W):
        count=0
        c1,c2,c3,c4=1,1,1,1
        if list[i][j]==".":
            for k in range(1,H+1):
                if i+k<H and c1:
                    if list[i+k][j]==".":
                       count+=1
                    else:
                       c1=0
                if i-k>=0 and c2:
                    if list[i-k][j]==".":
                       count+=1
                    else:
                       c2=0

            for k in range(1,W+1):
                if j+k<W and c3:
                    if list[i][j+k]==".":
                       count+=1
                    else:
                        c3=0
                if j-k>=0 and c4:
                    if list[i][j-k]==".":
                       count+=1
                    else:
                        c4=0
        if max<count:
            max=count
print(max+1)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
lis = [list(map(str,input().split("#"))) for i in range(h)]
li = []
for i in range(h):
  s = []
  for j in lis[i]:
    for n in range(len(j)):
      s.append(len(j))
    s.append(0)
  li.append(s)
l = []
for i in range(w):
  s = []
  cou = 0
  for j in range(h):
    if li[j][i] != 0:
      cou += 1
    else:
      cou = 0
    s.append(cou)
  for g in range(h-1):
    if s[-(2+g)] != 0 and s[-(2+g)] < s[-(1+g)]:
      s[-(2+g)] = s[-(1+g)]
  l.append(s)
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,li[i][j] + l[j][i]-1)
print(ans)

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(["#"]*w)
for i in range(h-2):
    a=input()
    s.append("#"+a+"#")
s.append(["#"]*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
            p+=yl[i][n]-yl[i][n-1]+tl[j][m]-tl[j][m-1]-3
            
            ans=max(ans,p)
                
        
print(ans)

Submission status: Time Limit Exceeded

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

graph_1 = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '.':
            if j != 0 and grid[i][j - 1] == '.':
                graph_1[i][j] = graph_1[i][j - 1] + 1
            else:
                graph_1[i][j] = 1

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

graph_2 = [[0] * W for _ in range(H)]
for j in range(W):
    for i in range(H):
        if grid[i][j] == '.':
            if i != 0 and grid[i - 1][j] == '.':
                graph_2[i][j] = graph_2[i - 1][j] + 1
            else:
                graph_2[i][j] = 1

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

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, graph_1[i][j] + graph_2[i][j] - 1)
        
print(ans)

Submission status: Time Limit Exceeded

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


def search(x, y):
    if not (0 <= x < H and 0 <= y < W):
        return False
    if F[x][y] == "#":
        return False
    else:
        return True


ans = 0
for i in range(H):
    for j in range(W):
        if F[i][j] == ".":
            count = 1
            x, y = i, j
            while True:
                if search(x, y+1):
                    count += 1
                    y += 1
                else:
                    break
            x, y = i, j
            while True:
                if search(x+1, y):
                    count += 1
                    x += 1
                else:
                    break
            x, y = i, j
            while True:
                if search(x-1, y):
                    count += 1
                    x -= 1
                else:
                    break
            x, y = i, j
            while True:
                if search(x, y-1):
                    count += 1
                    y -= 1
                else:
                    break
            if count > ans:
                ans = count

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

import sys, math, random
import numpy as np

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = [int(input()) for _ in range(N)] # 1 row N column
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
# S.replace('ABC','X') # "testABCABC" -> "testXX"
 
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
# def LLS(): return [list(map(str, l.split())) for l in sys.stdin.readlines()]
# def LLS(): return list(input()) for l in sys.stdin.readlines()]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    H, W = list(map(int,input().split()))
    S=[]
    for i in range(H):
        S.append(list(input()) )
    # print(S)
    S=np.asarray(S)

    R=np.zeros([H,W])
    C=np.zeros([W,H])
    # R[0,2:3]=
    for h,ss in enumerate(S):
        tmp=0
        for w,s in enumerate(ss):
            if s==".":
                tmp+=1
            else:
                R[h,w-tmp:w]=tmp
                tmp=0
        if tmp>0:
            R[h,w-tmp+1:w+1]=tmp
            tmp=0


    for h,ss in enumerate(S.T):
        tmp=0
        for w,s in enumerate(ss):
            if s==".":
                tmp+=1
            else:
                C[h,w-tmp:w]=tmp
                tmp=0
        if tmp>0:
            C[h,w-tmp+1:w+1]=tmp
            tmp=0
    out=int((R+C.T).max()-1)
    if out>0:
        print(out)
    else:
        print("0")
            # print(s)
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
class Data:
    def __init__(self):
        self.n = 0
    def __repr__(self):
        return str(self.n)
X = [[None for _ in range(W)] for _ in range(H)]
Y = [[None for _ in range(W)] for _ in range(H)]
start_h = [0 for _ in range(W)]
data_h = [Data() for _ in range(W)]
for h in range(H):
    start = 0
    data_w = Data()
    for w in range(W):
        if S[h][w] == ".":
            X[h][w] = data_w
            Y[h][w] = data_h[w]
            continue
        data_w.n = w - start
        start = w + 1
        data_w = Data()
        data_h[w].n = h - start_h[w]
        start_h[w] = h + 1
        data_h[w] = Data()
    else:
        if start < W:
            data_w.n = W - start
else:
    for w in range(W):
        if start_h[w] < H:
            data_h[w].n = H - start_h[w]
num = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        n = X[h][w].n + Y[h][w].n - 1
        num = max(n, num)
print(num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def cal(S, x):
    S1 = []
    for i in S:
        i = "".join(i)
        li1 = list(i)
        indexes = [i for i, x in enumerate(li1) if x == "#"]
        indexes.append(x+1)
        li2 = i.split("#")
        li3 = [len(s) for s in li2]
        
        cnt = 0
        ret = []
        b_index = 0
        for index in indexes:
            if cnt == 0:
                ret.extend( [li3[cnt] for _ in range(index-b_index)])
            else:
                ret.extend( [li3[cnt] for _ in range(index-b_index-1)])
            ret.append(0)
            b_index = index
            cnt += 1
        ret.pop()
        ret.pop()
        S1.append(ret)
    return np.array(S1)

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

S = []
for i in range(H):
    S.append(list(input()))
    
A = np.array(S)
B = A.T

S1 = cal(A,W)
S2 = cal(B,H)

XX = S1+S2.T

print(np.max(XX)-1)

Submission status: Time Limit Exceeded

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

ij = np.zeros([H,W])    # 横の.の連続数を格納用
ji = np.zeros([H,W])    # 縦の.の連続数を格納用

for i in range(H):
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ji[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ji[start:end+1, j] += cnt
            cnt = 0

iijj = ij + ji - 1  # 自分が2回足されるので、1引く
ans = int(iijj.max())
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int, input().split())
S=[input() for i in range(H)]
l=[[0]*W for i in range(H)]
r=[[0]*W for i in range(H)]
t=[[0]*W for i in range(H)]
b=[[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            l[h][w]=l[h][w-1]+1
            t[h][w]=t[h-1][w]+1
        if S[h][W-w-1]=='.':
            r[h][W-w-1]=r[h][-w]+1
        if S[H-h-1][w]=='.':
            b[H-h-1][w]=b[-h][w]+1
ans=0
for h in range(H):
    for w in range(W):
        ans=max(ans,l[h][w]+r[h][w]+t[h][w]+b[h][w]-3)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
X = [[-10**2 for __ in range(W)] for _ in range(H)]
Y = [[-10**2 for __ in range(W)] for _ in range(H)]
for y in range(H):
  last_x = -1
  for x in range(W):
    if S[y][x] == "#":
      for t in range(last_x+1,x):
        X[y][t] = x-1-last_x
      last_x = x
  for t in range(last_x+1,W):
    X[y][t] = W-1-last_x
for x in range(W):
  last_y = -1
  for y in range(H):
    if S[y][x] == "#":
      for t in range(last_y+1,y):
        Y[t][x] = y-1-last_y
      last_y = y
  for t in range(last_y+1,H):
    Y[t][x] = H-1-last_y
ans = 0
for y in range(H):
  for x in range(W):
    ans = max(ans, Y[y][x]+X[y][x])
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np

H, W = [int(x) for x in stdin.readline().rstrip().split()]
S = [stdin.readline().rstrip() for _ in range(H)]
S_new = np.array([[1 if S[k][l] == '#' else 0 for l in range(W)] for k in range(H)])
ans = 0
for y in range(H):
    for x in range(W):
        if S_new[y][x] == 1:
            continue
        cnt = 1
        for k in range(1, W - x):
            if S_new[y][x + k] == 1:
                break
            cnt += 1
        for l in range(1, x + 1):
            if S_new[y][x - l] == 1:
                break
            cnt += 1
        for m in range(1, H - y):
            if S_new[:, x][y + m] == 1:
                break
            cnt += 1
        for n in range(1, y + 1):
            if S_new[:, x][y - n] == 1:
                break
            cnt += 1
        ans = max(ans, cnt)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

S = [[0 for w in range(W)] for h in range(H)]
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 = [[0 for w in range(W)] for h in range(H)]

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 = [[0 for w in range(W)] for h in range(H)]

for w in range(W):
    se = []
    cnt = 0
    for h in range(H):
        val = S[h][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


mx = 0
for h in range(H):
    for w in range(W):
        mx = max(Sh[h][w] + Sw[h][w], mx)

print(max((mx-1,0)))

Submission status: Time Limit Exceeded

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

S = []

def search(a,b,x,y):
        try:
                if(S[a][b] == "#") or a<0 or b<0:
                        return 0
                else:
                        return search(a+x, b+y, x, y)+1
        except:
                return 0

for i in range(H):
        S.append(input())
ans = 0
for i in range(H):
        for j in range(W):
                vec = [(1,0), (0,1), (-1,0), (0,-1)]
                tmp = 1
                # print(i,j)
                for v in vec:
                        tmp += search(i,j,v[0], v[1])-1
                        # print(tmp)
                ans = max(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

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

for i in range(h):
    s = input()
    count = 0
    for j in range(w):
        if j != w-1:
            if s[j] == '.':
                count += 1
            else:
                li[i][j] = 0
                for k in range(count):
                    li[i][j-k-1] = count
                count = 0
        else:
            if s[j] == '.':
                count += 1
                for k in range(count):
                    li[i][j-k] = count
            else:
                li[i][j] = 0
                for k in range(count):
                    li[i][j-k-1] = count

for i in range(w):
    count = 0
    for j in range(h):
        if j != h-1:
            if li[j][i] > 0:
                count += 1
            else:
                for k in range(count):
                    li[j-k-1][i] += count
                count = 0
        else:
            if li[j][i] > 0:
                count += 1
                for k in range(count):
                    li[j-k][i] += count
            else:
                for k in range(count):
                    li[j-k-1][i] += count

ans = 0

for i in range(h):
    ans = max(ans,max(li[i]))

print(ans-1)