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)]
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 = [row[w] for row in S]
    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 = 1
for h in range(H):
    for w in range(W):
        ans = max(ans, count_math[h][w] + count_matw[h][w])
# print(count_math)
# print(count_matw)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
read = input 
rn = lambda :list(map(int, read().split()))
r, c = rn()
M = [
    list(read()) for i in range(r)
]
def init():
    return [
    [
        0 for i in range(c)
    ] for i in range(r)
] # padding
LEFT = init()
RIGHT = init()
UP = init()
DOWN = init()
# LEFT
for i in range(r):
    for j in range(c):
        if(M[i][j] == '#'):continue
        RIGHT[i][j] = 1
        if(j != 0 and M[i][j-1] == '.'):
            RIGHT[i][j] += RIGHT[i][j-1]
        
        DOWN[i][j] = 1
        if(i != 0 and M[i-1][j] == '.'):
            DOWN[i][j] += DOWN[i-1][j]
def reverse_range(r):return range(r-1, -1, -1)
for i in reverse_range(r):
    for j in reverse_range(c):
        if(M[i][j] == '#'):continue
            
        LEFT[i][j] = 1
        if(j != c-1 and M[i][j+1] == '.'):
            LEFT[i][j] += LEFT[i][j+1]
        
        UP[i][j] = 1
        if(i != r-1 and M[i+1][j] == '.'):
            UP[i][j] += UP[i+1][j] 
ans = 0
for i in range(r):
    for j in range(c):
        tmp = 0
        if(M[i][j] == '#'):continue
        tmp +=  UP[i][j] + DOWN[i][j] + LEFT[i][j] + RIGHT[i][j] - 3
        ans = max( ans, tmp,)
print(ans)

Submission status: Time Limit Exceeded

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

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(20000*20000)

from functools import lru_cache

################################################################################

H, W = list(map(int, input().split()))
OBS = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            OBS[i][j] = 1

@lru_cache(maxsize = None)
def dfs_horz_left(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_horz_left(i,j-1) if j != 0 else 1

@lru_cache(maxsize = None)
def dfs_horz_right(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_horz_right(i,j+1) if j != W-1 else 1

@lru_cache(maxsize = None)
def dfs_vert_up(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_vert_up(i-1,j) if i != 0 else 1

@lru_cache(maxsize = None)
def dfs_vert_down(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_vert_down(i+1,j) if i != H-1 else 1

best = 0
for i in range(H):
    for j in range(W):
        if OBS[i][j]:
            continue
        s = dfs_horz_left(i,j) + dfs_horz_right(i,j) + dfs_vert_up(i,j) + dfs_vert_down(i,j) - 3
        if s > best:
            best = s
print(best)

Submission status: Time Limit Exceeded

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

VT, HT = [], []
for i in range(H):
    line = input().strip()
    VT += [list(line)]
    HT += [list(line)]

# print(VT)

ans = 0
for row in range(H):
    for col in range(W):
        if VT[row][col] == '#':
            continue
        if HT[row][col] == '.':
            count = 0
            cpos = col
            while 0 <= cpos < W and HT[row][cpos] != '#':
                count += 1
                cpos += 1
            for c in range(col, cpos):
                HT[row][c] = count
        if VT[row][col] == '.':
            count = 0
            rpos = row
            while 0 <= rpos < H and VT[rpos][col] != '#':
                count += 1
                rpos += 1
            for r in range(row, rpos):
                VT[r][col] = count

        ans = max(ans, VT[row][col] + HT[row][col] - 1)

# print(HT)
# print(VT)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
#print(S)
dpyoko = [[1]*(W) for i in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            dpyoko[i][j] = 0
        else:
            if j != 0:
                dpyoko[i][j] += dpyoko[i][j-1]
dptate = [[1]*(W) for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            dptate[i][j] = 0
        else:
            if i != 0:
                dptate[i][j] += dptate[i-1][j]
#print(dpyoko)
#print(dptate)
for j in range(W-1,-1,-1):
    for i in range(H):
        if dpyoko[i][j] == 0:
            continue
        if j == W-1:
            continue
        dpyoko[i][j] = max(dpyoko[i][j],dpyoko[i][j+1])
#print(dpyoko)
for i in range(H-1,-1,-1):
    for j in range(W):
        if dptate[i][j] == 0:
            continue
        if i == H-1:
            continue
        dptate[i][j] = max(dptate[i][j],dptate[i+1][j])
#print(dptate)
dp = [[0]*(W) for i in range(H)]
res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        dp[i][j] = dptate[i][j]+dpyoko[i][j]-1 
        if res < dp[i][j]:
            res = dp[i][j]
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
input = sys.stdin.readline
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)
ans = [[1]*w for i in range(h)]
x = [[0]*w for i 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] = x[i][j-1] +1
                if s[i][j] == ".":
                        ans[i][j] += x[i][j]

x = [[0]*w for i in range(h)]
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] = x[i][j+1] +1
                if s[i][j] == ".":
                        ans[i][j] += x[i][j]
x = [[0]*w for i in range(h)]
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] = x[j+1][i] +1
                if s[j][i] == ".":
                        ans[j][i] += x[j][i]
x = [[0]*w for i in range(h)]
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] = x[j-1][i] +1
                if s[j][i] == ".":
                        ans[j][i] += x[j][i]               
ans2 = 0
for i in range(h):
        for j in range(w):
                ans2 = max(ans2,ans[i][j])
print(ans2)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

h,w = na()
dp = []
for i in range(h):
    s = ns()
    c = 0
    lst = []
    for j in s:
        if j == '.':
            c += 1
        else:
            for k in range(c):
                lst.append(c)
            lst.append(0)
            c = 0
    for k in range(c):
        lst.append(c)
    dp.append(lst)

ans = 0
for i in range(w):
    a = 0
    c = 0
    for j in range(h):
        t = dp[j][i]
        if t == 0:
            a = max(t,a)
            ans = max(ans,a+c)
            a = 0
            c = 0
        else:
            a = max(t,a)
            c += 1
    ans = max(ans,a+c)

print(ans-1)

Submission status: Time Limit Exceeded

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

import sys
sys.dont_write_bytecode = True
stdin = sys.stdin
input = stdin.readline
sys.setrecursionlimit(20000*20000)

from functools import reduce, lru_cache

################################################################################

H, W = list(map(int, input().split()))
OBS = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            OBS[i][j] = 1

@lru_cache(maxsize = H * W)
def dfs_horz_left(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_horz_left(i,j-1) if j != 0 else 1

@lru_cache(maxsize = H * W)
def dfs_horz_right(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_horz_right(i,j+1) if j != W-1 else 1

@lru_cache(maxsize = H * W)
def dfs_vert_up(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_vert_up(i-1,j) if i != 0 else 1

@lru_cache(maxsize = H * W)
def dfs_vert_down(i, j):
    if OBS[i][j]:
        return 0
    return 1+dfs_vert_down(i+1,j) if i != H-1 else 1

best = -1
for i in range(H):
    for j in range(W):
        if OBS[i][j]:
            continue
        s = dfs_horz_left(i,j) + dfs_horz_right(i,j) + dfs_vert_up(i,j) + dfs_vert_down(i,j) - 3
        if s > best:
            best = s
print(best)

Submission status: Time Limit Exceeded

Solution code:
def count(row):
    for i in range(1,len(row)):
        if row[i] == 0:
            continue
        row[i] += row[i-1]
    # print(row)

    for i in range(len(row)-2, -1, -1):
        if row[i] == 0:
            continue
        row[i] = max(row[i], row[i+1])
    # print(row)

    return row


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

    h = [[0 for j in range(H)] for i in range(W)]  # transpose
    w = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        for j in range(W):
            h[j][i] = 0 if ss[i][j] == "#" else 1
            w[i][j] = 0 if ss[i][j] == "#" else 1

    w = [count(r) for r in w]
    h = [count(r) for r in h]

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main(H, W, s_list):
    row_count = np.zeros((H, W))
    for i_row in range(H):
        i_col = 0
        j_col = 0
        while(i_col < W):
            char = s_list[i_row][i_col]
            j_col = i_col
            
            if char == '.':
                while(True):
                    j_col += 1
                    if j_col == W:
                        break
                    c = s_list[i_row][j_col]
                    if c == '#':
                        break

                row_count[i_row, i_col:j_col] = j_col - i_col
            i_col = j_col + 1


    col_count = np.zeros((H, W))
    for i_col in range(W):
        i_row = 0
        j_row = 0 
        while(i_row < H):
            char = s_list[i_row][i_col]
            j_row = i_row
            if char == '.':
                while(True):
                    j_row += 1
                    if j_row == H:
                        break
                    c = s_list[j_row][i_col]
                    if c == '#':
                        break
                
                col_count[i_row:j_row, i_col] = j_row - i_row
            i_row = j_row + 1
    print(int(np.max(row_count + col_count)) - 1)



if __name__ == "__main__":
    H, W = [int(x) for x in input().split()]
    s_list = []
    for _ in range(H):
        s_list.append(input())

    main(H, W, s_list)

Submission status: Time Limit Exceeded

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

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

a = -1
b = -1
for i in range(h):
    a = -1
    for j in range(w):
        if S[i][j] == "#":
            if a != -1:
                for k in range(a,j):
                    A[i][k] += j-a
                a = -1
        else:
            if a == -1:
                a = j
                #print(j)
    if a != -1:
        for k in range(a,j+1):
            A[i][k] += j+1-a

for i in range(w):
    a = -1
    for j in range(h):
        if S[j][i] == "#":
            if a != -1:
                for k in range(a,j):
                    A[k][i] += j-a
                a = -1
        else:
            if a == -1:
                a = j
    if a != -1:
        for k in range(a,j+1):
            A[k][i] += j+1-a
#print(A)

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

print(ans-1)

Submission status: Time Limit Exceeded

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

def keisan(h,w):
    k = 0
    while h-k>=0:
        if G[h-k][w] == ".":
            k += 1
        else:
            break
    l = 0
    while h+l<H:
        if G[h+l][w] == ".":
            l += 1
        else:
            break
    m = 0
    while w-m>=0:
        if G[h][w-m] == ".":
            m += 1
        else:
            break
    n = 0
    while w+n < W:
        if G[h][w+n] == ".":
            n += 1
        else:
            break
    return k+l+m+n-3

ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == ".":
                ans = max(ans,keisan(h,w))
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

def print_map(mp):
    for r in mp:
        print(['{:2d}'.format(n) for n in r])

H, W = map(int, input().split())
mp = [[0 for w in range(W)] for h in range(H)]
mp_row = [[0 for w in range(W)] for h in range(H)]
mp_col = [[0 for w in range(W)] for h in range(H)]
mp_sum = [[0 for w in range(W)] for h in range(H)]

# 0 = なし、 -1 = 障害物、 1=光
for h in range(H):
    s = input()
    for w in range(W):
        if s[w] == ".":
            mp[h][w] = 0
        else:
            mp[h][w] = -1

# 全探索はO(HWHW)となって爆発。
# 縦横でまずカウントするのがよさげ。

## 横のパネル数
for h in range(H):
    st = 0
    cnt = 0
    for w in range(W):
        if mp[h][w] == -1:
            for i in range(st, w):
                mp_row[h][i] = cnt
            cnt = 0
            st = w+1
        elif w == W-1:
            cnt += 1
            for i in range(st, W):
                mp_row[h][i] = cnt
        else:
            cnt += 1

## 縦のパネル数
for w in range(W):
    st = 0
    cnt = 0
    for h in range(H):
        if mp[h][w] == -1:
            for i in range(st, h):
                mp_col[i][w] = cnt
            cnt = 0
            st = h+1
        elif h == H-1:
            cnt += 1
            for i in range(st, H):
                mp_col[i][w] = cnt
        else:
            cnt += 1

#print_map(mp_row)
#print()
#print_map(mp_col)

mx = 0
for h in range(H):
    for w in range(W):
        mx = max(mx, mp_row[h][w]+mp_col[h][w]-1)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
res = [[0 for _ in range(w+1)] for _ in range(h)]
count = [0 for _ in range(w+1)]
for i in range(h):
  si = str(input())
  si = si + '#'
  r = 0
  for j in range(w+1):
    if si[j] == '#':
      for k in range(r):
        res[i][j-k-1] += r
      r = 0
      for k in range(count[j]):
        res[i-k-1][j] += count[j]
      count[j] = 0
    else:
      r += 1
      count[j] += 1
for j in range(w):
  for k in range(count[j]):
    res[h-k-1][j] += count[j]
ans = max(x for sub in res for x in sub)
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
X = [[0] * W for _ in range(H)]
for h in range(H):
    start = 0
    for w in range(W):
        if S[h][w] == ".":
            continue
        for i in range(start, w):
            X[h][i] = w - start
        start = w + 1
    else:
        for i in range(start, W):
            X[h][i] = W - start
Y = [[0] * H for _ in range(W)]
for w in range(W):
    start = 0
    for h in range(H):
        if S[h][w] == ".":
            continue
        for i in range(start, h):
            Y[w][i] = h - start
        start = h + 1
    else:
        for i in range(start, H):
            Y[w][i] = H - start
num = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        n = X[h][w] + Y[w][h] - 1
        num = max(n, num)
print(num)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product

h, w = map(int, input().split())
x = [list(input()) for _ in range(h)]
xh = [[0 for j in range(w)] for i in range(h)]
xw = [[0 for j in range(w)] for i in range(h)]
for j in range(w):
    u = 0
    for i in range(h):
        if x[i][j] == '#':
            for k in range(u, i):
                xh[k][j] = i - u
            u = i + 1
    for k in range(u, h):
        xh[k][j] = h - u

for i in range(h):
    l = 0
    for j in range(w):
        if x[i][j] == '#':
            for k in range(l, j):
                xw[i][k] = j - l
            l = j + 1
    for k in range(l, w):
        xw[i][k] = w - l
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, xh[i][j] + xw[i][j] - 1)
print(ans)

Submission status: Time Limit Exceeded

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

area_yoko = []
area_tate = []

for i in range(H):
	tmp = []
	yoko = S[i]
	area_start = 0
	kabe = yoko[0] == "#"
	j = 0
	while j < W:
		if yoko[j] == ".":
			if kabe:
				kabe = False
				area_start = j
			j += 1
			continue
		else:
			if not kabe:
				kabe = True
				length = j - area_start
				tmp.append((area_start, j-1, length))
			j += 1
			continue
	if not kabe:
		tmp.append((area_start, W-1, W-area_start))
	area_yoko.append(tmp)


for i in range(W):
	tmp = []
	tate = [S[j][i] for j in range(H)]
	area_start = 0
	kabe = tate[0] == "#"
	j = 0
	while j < H:
		if tate[j] == ".":
			if kabe:
				kabe = False
				area_start = j
			j += 1
			continue
		else:
			if not kabe:
				kabe = True
				length = j - area_start
				tmp.append((area_start, j-1, length))
			j += 1
			continue
	if not kabe:
		tmp.append((area_start, H-1, H-area_start))
	area_tate.append(tmp)

def search(x, area):
	l = 0
	r = len(area)
	while r-l > 1:
		p = (l+r)//2
		lower = area[p][0]
		upper = area[p][1]
		if lower <= x and x <= upper:
			return area[p]
		elif x < lower:
			r = p
		else:
			l = p
	lower,upper = area[l][0], area[l][1]
	if lower <= x and x <= upper:
		return area[l]
	else:
		return None
ans = 0
for y in range(H):
	for x in range(W):
		if S[y][x] != "#":
			yoko_info = search(x, area_yoko[y])
			tate_info = search(y, area_tate[x])
			ans = max(ans, yoko_info[2] + tate_info[2] - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            # ここで代入しておくことで、後の繰り返しを避ける
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    # 木の併合、入力は併合したい各ノード
    def Unite(self, x, y):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return
        # 違う木に属していた場合rnkを見てくっつける方を決める
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
      
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
    
UF = UnionFind(2*H*W)
## 横方向につながっているか
for i in range(H):
  hold = []
  for j in range(W):
    if S[i][j] == '#':
      hold = []
    elif len(hold) == 0:
      hold = [(i,j)]
    else:
      UF.Unite(hold[0][0]*W+hold[0][1], i*W+j)

## 縦方向につながっているか
for j in range(W):
  hold = []
  for i in range(H):
    if S[i][j] == '#':
      hold = []
    elif len(hold) == 0:
      hold = [(i,j)]
    else:
      UF.Unite(hold[0][0]*W+hold[0][1]+(H*W), i*W+j+(H*W))
      
solver = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    else:
      var = UF.Count(i*W+j) + UF.Count(i*W+j+(H*W)) - 1
      solver.append(var)

print(max(solver))

Submission status: Time Limit Exceeded

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



"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            dy = y
            while dy < H and grid[dy][x] != '#':
                dy += 1
            for yy in range(y, dy):
                if res_y[yy][x] == 0:
                    res_y[yy][x] = dy-y
            x += 1
        x = 0
        y += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
input = sys.stdin.readline
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
ans = 0
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
                if s[j][i] == ".":
                        ans = max(ans,sum(x[j][i])+1)                   
print(ans)

Submission status: Time Limit Exceeded

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

    field = [input() for _ in range(h)]

    points = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        left = 0
        for j in range(w):
            if field[i][j] == '#':
                for k in range(left, j):
                    points[i][k] += j-left
                left = j+1
                continue
        for k in range(left, w):
            points[i][k] += w-left

    #print("\n".join(str(point) for point in points))
    for j in range(w):
        up = 0
        for i in range(h):
            if field[i][j] == '#':
                for k in range(up, i):
                    points[k][j] += i-up
                up = i+1
                continue
        for k in range(up, h):
            points[k][j] += h-up

    psoudo_ans = max(max(line) for line in points)
    print(max(0, psoudo_ans-1))
    #print("\n".join(str(point) for point in points))


main()

Submission status: Time Limit Exceeded

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

grid = [input() for _ in range(h)]

field = [[0] * w for _ in range(h)]

for i, row in enumerate(grid):
    row = row + "#"
    cnt = row.count("#")

    idx = -1
    for j in range(cnt + 1):
        idx_next = row.find("#", idx + 1)
        for k in range(idx + 1, idx_next):
            field[i][k] = idx_next - idx - 1
        idx = idx_next

m = 0
for i, row in enumerate(zip(*grid)):
    row = "".join(row) + "#"
    cnt = row.count("#")

    idx = -1
    for j in range(cnt + 1):
        idx_next = row.find("#", idx + 1)
        for k in range(idx + 1, idx_next):
            field[k][i] += idx_next - idx - 1
            if field[k][i] > m:
                m = field[k][i]
        idx = idx_next

print(m - 1)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

import numpy as np

H, W = map(int, input().rstrip().split(' '))

field = np.zeros((H+2, W+2)) + 1
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '.':
            field[i+1, j+1] = 0
  
count_width = np.zeros((H, W))
for i in range(1, H+1):
    idx = np.where(field[i] == 1)[0]
    for j in range(1, len(idx)):
        count_width[i-1, idx[j-1]:idx[j]-1] = idx[j] - idx[j-1] - 1
        
count_height = np.zeros((H, W))
for i in range(1, W+1):
    idx = np.where(field[:,i] == 1)[0]
    for j in range(1, len(idx)):
        count_height[idx[j-1]:idx[j]-1, i-1] = idx[j] - idx[j-1] - 1
 
print(int(np.max(count_width + count_height)) - 1)

Submission status: Time Limit Exceeded

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

A = [[[0,0] for i in range(w)] for j in range(h)]

a = -1
b = -1
for i in range(h):
    a = -1
    for j in range(w):
        if S[i][j] == "#":
            if a != -1:
                for k in range(a,j):
                    A[i][k][0] = j-a
                a = -1
        else:
            if a == -1:
                a = j
                #print(j)
    if a != -1:
        for k in range(a,j+1):
            A[i][k][0] = j+1-a

for i in range(w):
    a = -1
    for j in range(h):
        if S[j][i] == "#":
            if a != -1:
                for k in range(a,j):
                    A[k][i][1] = j-a
                a = -1
        else:
            if a == -1:
                a = j
    if a != -1:
        for k in range(a,j+1):
            A[k][i][1] = j+1-a
#print(A)

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, A[i][j][0] + A[i][j][1])

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

is_wall = []  # is_wall[h][w]
for _ in range(h):
    is_wall.append(list(map(lambda c: c == "#", input())) + [True])
is_wall.append([True] * (w + 1))

x_sight = {}
buf = deque()
for y in range(h + 1):
    sight = 0
    buf.clear()
    for x in range(w + 1):
        if is_wall[y][x]:
            for i in buf:
                x_sight[i] = sight
            x_sight[(x, y)] = 0
            sight = 0
            buf.clear()
        else:
            buf.append((x, y))
            sight += 1

y_sight = {}
for x in range(w + 1):
    sight = 0
    buf.clear()
    for y in range(h + 1):
        if is_wall[y][x]:
            for i in buf:
                y_sight[i] = sight
            y_sight[(x, y)] = 0
            sight = 0
            buf.clear()
        else:
            buf.append((x, y))
            sight += 1

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(x_sight[(x, y)] + y_sight[(x, y)] - 1, ans)

print(ans)