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: Wrong Answer

Solution code:
def inpl():
    return list(map(int, input().split()))


H, W = inpl()
S = [input() + '#' for i in range(H)]
S.append("#" * (W + 1))

vertical = [0 for i in range(W + 1)]
side = [0 for i in range(W + 1)]
past_side = [0 for i in range(W + 1)]
ans = 0

for h in range(H + 1):
    start = 0
    keep = 0
    for w in range(W + 1):
        if S[h][w] == '#':
            for i in range(start, w):
                side[i] = max(side[i], keep)
            ans = max(ans, past_side[w] + vertical[w] - 1)

            keep = 0
            start = w + 1
            vertical[w] = 0
            side[w] = 0
        else:
            keep += 1
            vertical[w] += 1
        past_side[w] = side[w]
    # print(h, ans)
    # print(side)
    # print(vertical)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

val = list(map(int, input().strip().split()))
width = val[1]
height = val[0]

walls = np.zeros((height, width))

for y in range(height):
    val = input().strip()
    for x in range(width):
        walls[y, x] = 1 if val[x] == '#' else 0

left = np.zeros((height, width))
right = np.zeros((height, width))
up = np.zeros((height, width))
down = np.zeros((height, width))

# left
for y in range(height):
    cache = 0
    for x in range(width):
        if walls[y, x] == 1:
            cache = x + 1
            left[y, x] = 100
        else:
            left[y, x] = cache

# right
for y in range(height):
    cache = 0
    for x in range(width - 1, -1, -1):
        if walls[y, x] == 1:
            cache = width - x
        else:
            right[y, x] = cache

# up
for x in range(width):
    cache = 0
    for y in range(height):
        if walls[y, x] == 1:
            cache = y + 1
        else:
            up[y, x] = cache

# down
for x in range(width):
    cache = 0
    for y in range(height - 1, -1, -1):
        if walls[y, x] == 1:
            cache = height - y
        else:
            down[y, x] = cache

all = left + right + up + down
print(int(width + height - np.amin(all) - 1))

Submission status: Wrong Answer

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

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

max_row1=0
for i in range(h):
    tmp_row=0
    tmp_tmp_row=0
    for j in range(w):
        if s[i][j]=='#':
            if tmp_tmp_row<tmp_row:
                tmp_tmp_row=tmp_row
                tmp_row=0
                continue
            else:
                tmp_row=0
                continue
        else:
            tmp_row+=1
    print(tmp_row,tmp_tmp_row)
    if tmp_tmp_row>tmp_row:
        if tmp_tmp_row>max_row1:
            max_row1=tmp_tmp_row
    else:
        if tmp_row>max_row1:
            max_row1=tmp_row
max_col1=0
for j in range(w):
    tmp_col=0
    tmp_tmp_col=0
    for i in range(h):
        if s[i][j]=='#':
            if tmp_col>tmp_tmp_col:
                tmp_tmp_col=tmp_col
                tmp_col=0
                continue
            else:
                tmp_col=0
                continue
        else:
            tmp_col+=1
    if tmp_tmp_col>tmp_col:
        if tmp_tmp_col>max_col1:
            max_col1=tmp_tmp_col
    else:
        if tmp_col>max_col1:
            max_col1=tmp_col

print(max_col1+max_row1-1)

Submission status: Wrong Answer

Solution code:
import numpy as np
h, w = map(int, input().split())
s = []
for i in range(h):
  s.append(list(input()))
r1 = np.zeros((h, w))
for i in range(h):
  tmp = []
  for j in range(w):
    if s[i][j] == '#':
      if len(tmp) > 0:
        r1[i][tmp[0]:tmp[0]+len(tmp)]
        tmp = []
    else:
      tmp.append(j)
  else:
    if len(tmp) > 0:
      r1[i][tmp[0]:tmp[0]+len(tmp)] = len(tmp)
s = list(zip(*s))
r2 = np.zeros((w, h))
for i in range(w):
  tmp = []
  for j in range(h):
    if s[i][j] == '#':
      if len(tmp) > 0:
        r2[i][tmp[0]:tmp[0]+len(tmp)]
        tmp = []
    else:
      tmp.append(j)
  else:
    if len(tmp) > 0:
      r2[i][tmp[0]:tmp[0]+len(tmp)] = len(tmp)
print(int(np.max(r1 + r2.T - 1)))

Submission status: Wrong Answer

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)
print (ans)

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: Wrong Answer

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

memo_yoko1 = [[-1 for i in range(w)] for j in range(h)]
memo_tate1 = [[-1 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][0][j] == '.':
            if j == 0:
                memo_yoko1[i][j] = 1
            else:
                memo_yoko1[i][j] = memo_yoko1[i][j-1] + 1

            if i == 0:
                memo_tate1[i][j] = 1
            else:
                memo_tate1[i][j] = memo_tate1[i-1][j] + 1
        else:
            memo_yoko1[i][j] = 0
            memo_tate1[i][j] = 0

# transpose
s_t = [[''] for j in range(h)]
for i in range(h):
    s_t[i] = s[h - i - 1][0][::-1]

memo_yoko2 = [[-1 for i in range(w)] for j in range(h)]
memo_tate2 = [[-1 for i in range(w)] for j in range(h)]

for i in range(h):
    for j in range(w):
        if s_t[i][j] == '.':
            if j == 0:
                memo_yoko2[i][j] = 1
            else:
                memo_yoko2[i][j] = memo_yoko2[i][j-1] + 1

            if i == 0:
                memo_tate2[i][j] = 1
            else:
                memo_tate2[i][j] = memo_tate2[i-1][j] + 1
        else:
            memo_yoko2[i][j] = 0
            memo_tate2[i][j] = 0


ans = -1
for i in range(h):
    for j in range(w):
        _memo = memo_tate1[i][j] + memo_tate2[i][j] + memo_yoko1[i][j] + memo_yoko2[i][j]

        ans = max(ans, _memo)

print(ans - 4)

Submission status: Wrong Answer

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

sh = "#" * (w+2)
T = [sh]
for i in range(h):
    T.append("#"+S[i]+"#")
T.append(sh)

U = [[] for i in range(h+2)]
V = [[] for i in range(w+2)]
for i in range(h+2):
    for j in range(w+2):
        if T[i][j] == "#":
            U[i].append(j)
            V[j].append(i)

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

for i in range(len(U)):
    #print(U[i])
    for j in range(len(U[i])-1):
        #print(j)
        #print(U[i][j+1])
        for k in range(U[i][j]+1, U[i][j+1]):
            A[i][k] += U[i][j+1]-U[i][j]-1
for i in range(len(V)):
    for j in range(len(V[i])-1):
        for k in range(V[i][j]+1, V[i][j+1]):
            A[k][i] += V[i][j+1]-V[i][j]-1

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

print(ans-1)

Submission status: Wrong Answer

Solution code:
h, w=map(int, input().split())
kukan=[]
for i in range(h):
    s=list(input())
    index_left=0
    for j in range(w):
        if s[j]=="#":
            index_right=j
            if not index_left==index_right:
                kukan.append((index_left, index_right-1, index_right-1-index_left))
                index_left=index_right+1
            else:
                index_left=index_right+1
    if index_left-(w-1)<=0:
        kukan.append((index_left, w-1, w-1-index_left))
maximum=0

for i in range(h):
    lis=[]
    width=0
    for j in range(len(kukan)):
        if kukan[j][0]<=i<=kukan[j][1]:
            lis.append(j)
            width=max(width, kukan[j][2])

    maximum=max(maximum, len(lis)+width)




print(maximum)

Submission status: Wrong Answer

Solution code:
H,W  = map(int, input().split())
grid_w = []
grid = []
for i in range(H):
    S = input()
    tmp = [len(i) for i in S.split('#')]
    grid.append('#'.join([s.replace('.', str(t)) for t, s in zip(tmp, S.split('#'))]))
mx = 0
for i in range(W):
    S = ''.join([s[i] for s in grid])
    tmp = [len(i) for i in S.split('#')]
    k = 0
    for j in S:
        if j == '#':
            k += 1
            continue
        if int(j) + tmp[k] -1 > mx:
            mx = int(j) + tmp[k] -1
print(mx)

Submission status: Wrong Answer

Solution code:
#import numpy as np

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

S = [list(input()) for i in range(H)]
#print("S", S)

#map_yoko = np.zeros((H, W), dtype=int)
map_yoko = [ [0]*W for _ in range(H)]
map_tate = [ [0]*W for _ in range(H)]
#map_tate = np.zeros((H, W), dtype=int)

# yoko
for i in range(H):
    count = 0
    kabe = True
    start = None
    end = None
    for j in range(W):
        if S[i][j] == "#":
            end = j-1
            kabe = True
            
            #print(i, j, start, end, count)
            #if start is not None:
            if count >= 1:
                for k in range(start, end):
                    map_yoko[i][k] = count
            count = 0

        else:
            count += 1
            if kabe:
                kabe = False
                start = j

            if j == W-1:
                end = j
                for k in range(start, end):
                    map_yoko[i][k] = count


# tate
for j in range(W):
    count = 0
    kabe = True
    start = None
    end = None
    for i in range(H):
        if S[i][j] == "#":
            end = i-1
            kabe = True
            
            if count >= 1:
                for k in range(start, end):
                    map_tate[k][j] = count
            count = 0

        else:
            count += 1
            if kabe:
                kabe = False
                start = i

            if i == H-1:
                end = i
                for k in range(start, end):
                    map_tate[k][j] = count

#import numpy as np
#print("yoko\n", np.asarray(map_yoko))
#print("tate\n", np.asarray(map_tate))


out = 0
for i in range(H):
    for j in range(W):
        out = max(out, map_yoko[i][j] + map_tate[i][j])

#map_ = map_yoko + map_tate
#out = max(map_) - 1
out = max(0, out - 1)
print(out)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W = map(int,input().split())
square = []
for i in range (H):
    W_list = list(input())
    square.append(W_list)
    
    
square = np.array(square)

squareW =square.copy()
squareH =square.copy()


for h in range (H):
    counter = 0
    stock = 0
    for w in range (W):
        if squareW[h][w] == '#':
            squareW[h][stock:w] = counter 
            squareW[h][w] = 0
            counter = 0
            stock = w +1
        elif w == W-1:
            squareW[h][stock:] = counter +1
        else:
            counter +=1
            
for w in range (W):
    counter = 0
    stock = 0
    for h in range (H):
        if squareH[h][w] == '#':
            squareH[stock:h,w] = counter 
            squareH[h][w] = 0
            counter = 0
            stock = h +1
        elif h == H-1:
            squareH[stock:,w] = counter+1
        else:
            counter +=1
        
print(max((squareW.astype(int)+squareH.astype(int)).flatten())-1)

Submission status: Wrong Answer

Solution code:
import numpy as np


def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)


def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g




h,w = map(int,input().split())
m = [[0 for i in range(w)] for j in range(h)]
add_m = [[0 for i in range(w)] for j in range(h)]
test = [[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] == ".":
            m[i][j] = 0
        else:
            m[i][j] = 1
# print(m)

for i in range(h):
    s = 0
    length = 0
    flag = True
    for j in range(w):
        if m[i][j] == 1:
            for k in range(s, j):
                add_m[i][k] += length
            flag = False
        else:
            if flag:
                length += 1
            else:
                flag = True
                length = 1
                s = j
                # print(s)
    if flag:
        for k in range(s, w):
            add_m[i][k] += length
# print(add_m)

for i in range(w):
    s = 0
    length = 0
    flag = True
    for j in range(h):
        if m[j][i] == 1:
            for k in range(s, j):
                test[k][i] += length
                add_m[k][i] += length

            flag = False
        else:
            if flag:
                length += 1
            else:
                flag = True
                length = 1
                s = j
                # print(s)
    if flag:
        for k in range(s, h):
            test[k][i] += length
            add_m[k][i] += length

# print(test)
# print(add_m)

arr = np.array(add_m)
arr = arr.reshape(-1)
ans = np.max(arr)
print(ans-1)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ll = [[] for i in range(w)]
l = []
dpl = [[0]*h for i in range(w)]
dml= [[0]*w for i in range(h)]

for i in range(h):
    tl = input()
    l.append(tl)
    for n,j in enumerate(tl):
        ll[n].append(j)

for n,i in enumerate(l):
    s = 0
    t = 0
    for m,j, in enumerate(i):
        if s == 0 and j ==".":
            s+=1
            t = m
        elif j == ".":
            s+=1
        else:
            for r in range(t,m):
                dml[n][r] = s
            s = 0
    if i[-1] == ".":
        for r in range(t,w):
            dml[n][r] = s
for n,i in enumerate(ll):
    s = 0
    t = 0
    for m,j, in enumerate(i):
        if s == 0 and j ==".":
            s+=1
            t = m
        elif j == ".":
            s+=1
        else:
            for r in range(t,m):
                dpl[n][r] = s
            s = 0
    if i[-1] == ".":
        for r in range(t,h):
            dpl[n][r] = s


a = -1
for i in range(h):
    for j in range(w):
        a = max(a,dml[i][j]+dpl[j][i])
print(a-1)

Submission status: Wrong Answer

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

map_=[[0]*W for _ in range(H)]
for i in range(H):
    cnt=0
    q=[]
    for j in range(W+1):
        if S[i][j]=="#" and cnt!=0:
            for Q in q:
                map_[Q[0]][Q[1]]=cnt
            cnt=0
        elif S[i][j]==".":
            cnt+=1
            q.append([i,j])
for j in range(W):
    cnt=0
    q=[]
    for i in range(H+1):
        if S[i][j]=="#" and cnt!=0:
            for Q in q:
                map_[Q[0]][Q[1]]+=cnt
            cnt=0
        elif S[i][j]==".":
            cnt+=1
            q.append([i,j])
print(max([max(i) for i in map_])-1)

Submission status: Wrong Answer

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

S = []

Hv = []

for i in range(H):
    s_i = input()
    S.append(s_i)
    count = 0
    start = 0
    values = [0] * W
    while True:
        index = s_i.find('#', start)
        if index == -1:
            break

        if index == 0:
            start = index + 1
            continue

        val = index - start
        for y in range(start, index):
            values[y] = val
        start = index + 1

    val = W - start
    for y in range(start, W):
        values[y] = val

    Hv.append(values)


result = 0

for i in range(H):
    for j in range(W):
        val = Hv[i][j]
        for ii in range(i-1, -1, -1):
            if S[ii][j] == '#':
                break
            else:
                val += 1

        for ii in range(i+1, H, 1):
            if S[ii][j] == '#':
                break
            else:
                val += 1
        
        if val > result:
            result = val

print(result)

Submission status: Wrong Answer

Solution code:
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 = [0]
    x = 0
    for c in range(W):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(W, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    row_blocks.append(t)
# print(row_blocks)

col_blocks = []
for c in range(W):
    t = [0]
    x = 0
    for r in range(H):
        if s[r][c] == '.':
            x += 1
        else:
            x = 0
        t.append(x)

    x = 0
    for i in range(H, -1, -1):
        if t[i] > 0:
            x = max(x, t[i])
        else:
            x = 0
        t[i] = x
    col_blocks.append(t)
# print(col_blocks)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans = 1

def dfs(x,y,h,w):
  cnt = 1
  for i in range(1,w+2):
    if l[x+i][y] == '.':
      cnt += 1
    else:
      break
  for i in range(1,w+2):
    if l[x-i][y] == '.':
      cnt += 1
    else:
      break
  for i in range(1,h+2):
    if l[x][y+i] == '.':
      cnt += 1
    else:
      break
  for i in range(1,h+2):
    if l[x][y-i] == '.':
      cnt += 1
    else:
      break
  return cnt
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans,dfs(i,j,h,w))
print(ans)

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
l=['#'*(w+2)]+['#'+input()+'#' for i in range(h)]+['#'*(w+2)]
ans = 1

def dfs(x,y,h,w):
  cnt = 1
  for i in range(1,w+2):
    if l[x+i][y] == '.':
      cnt += 1
    else:
      break
  for i in range(1,w+2):
    if l[x-i][y] == '.':
      cnt += 1
    else:
      break
  for i in range(1,h+2):
    if l[x][y+i] == '.':
      cnt += 1
    else:
      break
  for i in range(1,h+2):
    if l[x][y-i] == '.':
      cnt += 1
    else:
      break
  return cnt
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans = max(ans,dfs(i,j,h,w))
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

yoko = []
for h in range(H):
  yoko.append(len(max(S[h].split("#"))))

tate = []
for hw in zip(*S):
  hw = "".join(hw)
  tate.append(len(max(hw.split("#"))))

ans = 0
for y in yoko:
  for t in tate:
    ans = max(ans, y+t-1)
print(ans)

Submission status: Wrong Answer

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

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

max_row1=0
for i in range(h):
    tmp_row=0
    tmp_tmp_row=0
    for j in range(w):
        if s[i][j]=='#':
            if tmp_tmp_row<tmp_row:
                tmp_tmp_row=tmp_row
                tmp_row=0
                continue
        else:
            tmp_row+=1
    if tmp_tmp_row>tmp_row:
        if tmp_tmp_row>max_row1:
            max_row1=tmp_tmp_row
    else:
        if tmp_row>max_row1:
            max_row1=tmp_row
max_col1=0
for j in range(w):
    tmp_col=0
    tmp_tmp_col=0
    for i in range(h):
        if s[i][j]=='#':
            if tmp_col>tmp_tmp_col:
                tmp_tmp_col=tmp_col
                tmp_col=0
                continue
        else:
            tmp_col+=1
    if tmp_tmp_col>tmp_col:
        if tmp_tmp_col>max_col1:
            max_col1=tmp_tmp_col
    else:
        if tmp_col>max_col1:
            max_col1=tmp_col

print(max_col1+max_row1-1)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[-1] * (W+2) for i in range(H+2)]
lst_shita = [[-1] * (W+2) for i in range(H+2)]
lst_migi = [[-1] * (W+2) for i in range(H+2)]
lst_hidari = [[-1] * (W+2) for i in range(H+2)]

# print (lst_ue)
def ue(i, j):
    if lst_ue[i][j] != -1:
        return lst_ue[i][j]
    if lst[i][j] == '#':
        lst_ue[i][j] = 0
        return 0
    else:
        lst_ue[i][j] = ue(i-1, j) + 1
        return lst_ue[i][j]


def shita(i, j):
    if lst_shita[i][j] != -1:
        return lst_shita[i][j]
    if lst[i][j] == '#':
        lst_shita[i][j] = 0
        return 0
    else:
        lst_shita[i][j] = shita(i+1, j) + 1
        return lst_shita[i][j]        


def hidari(i, j):
    if lst_hidari[i][j] != -1:
        return lst_hidari[i][j]
    if lst[i][j] == '#':
        lst_hidari[i][j] = 0
        return 0
    else:
        lst_hidari[i][j] = hidari(i, j-1) + 1
        return lst_hidari[i][j]        

def migi(i, j):
    if lst_migi[i][j] != -1:
        return lst_migi[i][j]
    if lst[i][j] == '#':
        lst_migi[i][j] = 0
        return 0
    else:
        lst_migi[i][j] = migi(i, j+1) + 1
        return lst_migi[i][j]        


if H > 1500 and W > 1500:
    print (H+W-1)
    sys.exit()

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if lst[i][j] != '#':
            ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
            if ans == H + W -1:
                print (ans)
                sys.exit()
# else:
#     for i in range(750,1250):
#         for j in range(750, 1250):
#             if lst[i][j] != '#':
#                 ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
#                 if ans == H+W-1:
#                     print (ans)
#                     sys.exit()

print (ans)

Submission status: Wrong Answer

Solution code:
import sys
inpt = sys.stdin.readline
import numpy as np

def cnt(lines, anc_n, anc_m, N, M):
  if lines[anc_n][anc_m]=='#':
    return 0
  
  n_min, n_max = 0, N
  for i in range(1, N-anc_n):
    if lines[anc_n+i][anc_m]=='#':
      n_max = anc_n + i-1
      break
  for i in range(1, anc_n+1):
    if lines[anc_n-i][anc_m]=='#':
      n_min = anc_n - i-1
      break
    
  m_min, m_max = 0, M
  for i in range(1, M-anc_m):
    if lines[anc_n][anc_m+i]=='#':
      m_max = anc_m + i-1
      break
  for i in range(1, anc_m+1):
    if lines[anc_n][anc_m-i]=='#':
      m_min = anc_m - i-1
      break
  return (n_max-n_min)+(m_max-m_min)


N, M = (int(d) for d in inpt().split())

ns_max_idx = []
ns_max = -float('inf')
ms_cnt = np.zeros(M, dtype=np.int64)
lines = []
for i in range(N):
  line = inpt().strip()
  lines.append(line)
  n_dot = line.count('.')
  if n_dot>ns_max:
    ns_max_idx.insert(0, i)
    ns_max = n_dot
  else:
    ns_max_idx.append(i)
  ms_cnt += [1 if d=='.' else 0 for d in line]

ms_max_idx = np.argsort(ms_cnt)[::-1]
out = [cnt(lines, anc_n, anc_m, N, M) for anc_n, anc_m in zip(ns_max_idx, ms_max_idx)]
print(max(out))

Submission status: Wrong Answer

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

yoko = 0
for h in range(H):
  yoko = max(len(max(S[h].split("#"))), yoko)

tate = 0
for hw in zip(*S):
  hw = "".join(hw)
  tate = max(len(max(hw.split("#"))), tate)
print(tate+yoko-1)

Submission status: Wrong Answer

Solution code:
#import numpy as np

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

S = [list(input()) for i in range(H)]
#print("S", S)

#map_yoko = np.zeros((H, W), dtype=int)
map_yoko = [ [0]*W for _ in range(H)]
map_tate = [ [0]*W for _ in range(H)]
#map_tate = np.zeros((H, W), dtype=int)

# yoko
for i in range(H):
    count = 0
    kabe = True
    start = None
    end = None
    for j in range(W):
        if S[i][j] == "#":
            end = j-1
            kabe = True
            
            #print(i, j, start, end, count)
            #if start is not None:
            if count >= 1:
                for k in range(start, end):
                    map_yoko[i][k] = count
            count = 0

        else:
            count += 1
            if kabe:
                kabe = False
                start = j

            if j == W-1:
                end = j
                for k in range(start, end):
                    map_yoko[i][k] = count


# tate
for j in range(W):
    count = 0
    kabe = True
    start = None
    end = None
    for i in range(H):
        if S[i][j] == "#":
            end = i-1
            kabe = True
            
            if count >= 1:
                for k in range(start, end):
                    map_tate[k][j] = count
            count = 0

        else:
            count += 1
            if kabe:
                kabe = False
                start = i

            if i == H-1:
                end = i
                for k in range(start, end):
                    map_tate[k][j] = count

#import numpy as np
#print("yoko\n", np.asarray(map_yoko))
#print("tate\n", np.asarray(map_tate))


out = 0
for i in range(H):
    for j in range(W):
        out = max(out, map_yoko[i][j] + map_tate[i][j])

#map_ = map_yoko + map_tate
#out = max(map_) - 1
out = out - 1
print(out)

Submission status: Wrong Answer

Solution code:
H,W  = map(int, input().split())
grid_w = []
grid = []
for i in range(H):
    S = input()
    tmp = [len(i) for i in S.split('#')]
    grid.append('#'.join([s.replace('.', str(t)) for t, s in zip(tmp, S.split('#'))]))
for i in range(W):
    tmp = ''.join([s[i] for s in grid])
    grid_w.append(max([max([int(j)+len(i)-1 for j in i]) if i else 0 for i in tmp.split('#')]))
print(max(grid_w))

Submission status: Wrong Answer

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())

    obs_h = defaultdict(list)
    obs_w = defaultdict(list)

    grid = []
    for _ in range(H):
        w = list(input())
        grid.append(w)

    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                obs_h[h].append(w)
                obs_w[w].append(h)

    def count(i, j):
        h_val = 0
        h_list = obs_h[i]
        # print(h_list)
        if len(h_list) == 0:  # 全部行ける
            h_val += W
        else:
            # print(h_list)
            h_index = bisect.bisect_right(h_list, i)
            if h_index == 0:
                h_val += h_list[0]
            elif h_index == len(h_list):
                h_val += W - h_list[-1] - 1
            else:
                h_val += h_list[h_index] - h_list[h_index - 1] - 1

        w_val = 0

        w_list = obs_w[j]
        if len(w_list) == 0:  # 全部行ける
            w_val += H
        else:
            w_index = bisect.bisect_right(w_list, j)
            if w_val == 0:
                w_val += w_list[0]
            elif w_index == len(w_list):
                w_val += H - w_list[-1] - 1
            else:
                w_val += w_list[w_index] - w_list[w_index - 1] - 1

        # print('hval = {}, wval = {}'.format(h_val, w_val))
        val = h_val + w_val
        if h_val > 0 and w_val > 0:
            val -= 1
        return val

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = input()
T = ['' for j in range(W)]
for j in range(W):
    for i in range(H):
        T[j] += S[i][j]
print(T)
yoko = [[0 for j in range(W)] for i in range(H)]
tate = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    idx = [j for j, x in enumerate(S[i]) if x == '#']
    idx.append(W)
    count = 0
    for j in range(W):
        if j == idx[count]:
            count += 1
        else:
            if count >= 1:
                yoko[i][j] = idx[count] - idx[count-1] - 1
            else:
                yoko[i][j] = idx[count]

for j in range(W):
    idx = [i for i, x in enumerate(T[j]) if x == '#']
    idx.append(H)
    count = 0
    for i in range(H):
        if i == idx[count]:
            count += 1
        else:
            if count >= 1:
                tate[i][j] = idx[count] - idx[count-1] - 1
            else:
                tate[i][j] = idx[count]
maxdp = 0
for i in range(H):
    for j in range(W):
        maxdp = max(maxdp, tate[i][j] + yoko[i][j]-1)
print(maxdp)

#print(yoko)
#print(tate)